题解 | #质因数的个数#

本题的关键点是两个sqrt()：

第一个sqrt

第一个sqrt出现在用埃拉托斯特尼筛法求一个范围的素数时，当我们在求1到s中谁是素数时，只需遍历到sqrt(s)即可，因为大于sqrt(s)的合数一定是由某些小于sqrt(s)的数组成的，那就一定在遍历到sqrt(s)时被定义为合数了。

第二个sqrt

第二个sqrt出现在：到底是求1到n的素数，还是求1到sqrt(n)的素数时。这里我们并不需要得到1到n的素数，因为若n有质因数大于sqrt(n)，那必然是只有一个（因为两个sqrt(n)的素数相乘一定大于n了），所以我们只需要求1到sqrt(n)的素数

#include <bits/stdc++.h>
#include <cmath>
#include <vector>
using namespace std;

vector<int> getprime(int s){   //s = sqrt(n)
    vector<int> all(s + 1, 1);
    all[0] = 0;
    all[1] = 0;

    int _s = sqrt(s);

    for(int i = 2; i <= _s; i++){
        if(all[i] == 1){
            for(int j = i; j * i <= s; j++){
                all[i * j] = 0;
            }
        }
    }

    vector<int> prime;

    for(int i = 2;i <= s; i++){
        if(all[i] == 1) prime.push_back(i);
    }

    return prime;

}


int main() {
    int n;
    while (cin >> n) {
        vector<int> prime = getprime(sqrt(n));
        int ans = 0;
        for(int i = 0; i < prime.size(); i++){
            while(n % prime[i] == 0){
                n /= prime[i];
                ans++;
            }
        }
        if(n > 1) ans++;

        cout << ans << '\n';


    
    }
}
// 64 位输出请用 printf("%lld")