题解 | #质因数的个数#

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_NUM = 4e4;

/**
 * 保存素数
 */
vector<int> primeNum;

/**
 * 标记素数
 */
bool isPrimeNum[MAX_NUM];

/**
 * 初始化 isPrimeNum[]数组
 */
void init();

/**
 * 质因数的个数--清华大学
 * @return
 */
int main() {
    init();
    int n;
    while (cin >> n) {
        int count = 0;
        for (int i = 0; i < primeNum.size() && primeNum[i] < n; ++i) {
            int factor = primeNum[i];
            //n能整除质因数
            while (n % factor == 0) {
                n /= factor;
                count++;
            }
        }
        //还存在一个大于sqrt(n)的质因数
        if (n > 1) {
            count++;
        }
        cout << count << endl;
    }

    return 0;
}

void init() {
    //初始化
    for (int i = 0; i < MAX_NUM; ++i) {
        isPrimeNum[i] = true;
    }
    /*
     * 0、1都不是素数
     */
    isPrimeNum[0] = false;
    isPrimeNum[1] = false;
    //从2开始遍历
    for (int i = 2; i < MAX_NUM; ++i) {
        if (!isPrimeNum[i]) {
            //数字i为非素数，则直接跳过
            continue;
        } else {
            //数字i为素数
            primeNum.push_back(i);
            /*
             * 若 i * i > MAX_NUM，则不用再循环了
             */
            if (i > MAX_NUM / i) {
                continue;
            }
            /*
             * 素数的整数倍为非素数
             * 直接从 i * i 开始循环，减少重复的工作，同时j += i，以保证j是i的整数倍
             * 为何从i*i开始呢？
             * 因为，i*k（其中k<i）必定已经在求k的某个素因数（必定小于i）时被标记过了，即i*k同时也是k的素因数的倍数。
             * 举例，标记素数3的倍数是，3 * 2 = 6，已经在标记素数2的倍数时被标记了，因此我们直接从3 * 3 = 9开始标记
             */
            for (int j = i * i; j < MAX_NUM; j += i) {
                isPrimeNum[j] = false;
            }
        }
    }
}