题解 | 质因数的个数

人类分解质因数的方法中最为常见的是辗转相除法（Euclid算法）。通过不断除以能够整除原数的质数，原数可以被不断缩小，进而更容易通过目视得到更多的其他质因数。

对于在代码中的实现，考虑从2开始从小到大寻找整除原数的数；如果能够整除则立即整除。之所以不用确定是否是质数，是因为如果这个待检测的数为合数，则这个数的所有质因数一定已经在先前的辗转相除中完成（如，在寻找到的时候显然已经将和全部除掉，因此此时已经无法被整除）。辗转相除的最终结果一定也是质数，这可以看作是再除以这个质数后得到结果；此时终止寻找即可。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_DEPRECATE

int main() {
    int N;
    while (std::cin >> N) {
        int primeFactor = 2, result = 0;
        while (N != 1) {
            if (!(N % primeFactor)) {
                N /= primeFactor;
                result++;
            } else primeFactor++;
        }
        std::cout << result << std::endl;
    }
}