题解 | #质因数的个数#

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

/*预先筛选题面数据范围内的素数
* 题面范围N，筛选到maxN=sqrt(N)+1
* 原因：
* N最多存在一个>maxN的质因数（否则两个大于maxN的质因数乘起来>N）
* 只需将<=maxN的素因数从n中去除
* 剩余的部分必为>maxN的质因数（至多有一个）
* 不必测试maxN到n的素数
* 如果除完<maxN的素因数后，n>1;
* 表明n存在一个大于MAXN的因子且为质因子
* 其幂指数也必定为1
*/

/*对于输入n
* 1 遍历<n的素数，判断是否为n的因数
* 2 确定某素数是因数
* 3 试除，确定幂指数
*/

const int N = 1e9;
//const int maxN=sqrt(N)+1; //就会报错，有很大问题
const int maxN = 31623;

vector<int> prime;
bool isPrime[31623];
//如果用注释的那种方法会报错：
//error: array bound is not an interger constant before ']' token

void Initial() { //初始化isPrime数组，和prime向量
    for (int i = 0; i < maxN; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = true;
    for (int i = 2; i < maxN; i++) {
        if (isPrime[i] == true) {
            prime.push_back(i);
            for (int j = i * i; j < maxN; j += i) {
                isPrime[false];
            }
        }
    }
    return ;
}


int main() {
    Initial();
    int n;
    while (scanf("%d", &n)!=EOF) {
        int answer = 0;
        int total = prime.size();
        for (int i = 0; prime[i] < n && i < total; i++) {
            if (n % prime[i] == 0) {
                n /= prime[i];
                answer++;
                while (n % prime[i] == 0) { //继续试除
                    n /= prime[i];
                    answer++;
                }
            }
        }
        if (n > 1) {
            answer++;
        }
        printf("%d\n", answer);
    }
    return 0;
}

error: variable length array declaration not allowed at file scope

array bound is not an interger constant before ']' token

注意全局变量数组长度的定义！！（在dev-c++上面能过有些OJ也有可能出问题）