题解 | #质因数的个数#

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#include <cmath>
using namespace std;


bool isprime[100000]; //isprime[i] 表示i这个数是不是素数
vector<int> prime; //保存素数

void Initial() { //初始化函数
    for (int i = 0; i < 100000; i++) { //初始化
        isprime[i] = true;
    }
    isprime[0] = false;
    isprime[1] = false;

    for (int i = 2; i < 100000; i++) {
        if (!isprime[i]) { //跳过不是素数的
            continue;
        }
        prime.push_back(i); //i为素数
        for (int j = i * i; j < 100000; j += i) { //素数的倍数不是素数
            isprime[j] = false;
        }
    }

}

int main() {
    Initial();
    int n;
    while (scanf("%d", &n) != EOF) {
        int res = 0;

        for (int i = 0; i < prime.size() && prime[i] < n; i++) {
            int factor = prime[i];
            while (n % factor == 0) {
                n /= factor;
                res++;
            }
        }
        if (n > 1) { //存在一个大于100000的因子
            res++;
        }
        printf("%d\n", res);
    }
    return 0;
}

n至多只存在一个大于sqrt(n)的素因子，因为如果有两个，那么乘积会大于n