我们知道，对于任意一个大于1的整数，它都可以分解成多个质因子相乘的形式。

质因数个数
题目描述：
求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入描述：
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出描述：
对于每组数据，输出N的质因数的个数。
输入样例#:
120
输出样例#:
5
题目来源：
DreamJudge 1156

题目解析：我们可以通过上一节学会的素数筛选，先将所有的素数筛选出来。然后再不断的去分解素数，直到将数分解到1为止。由于我们的素数筛选只能到1000000，对于更大的素因子我们可以不继续分解，因为不会存在两个大于1000000的素因子，如果存在，那么这个数的范围一定大于题目所给的范围10^9。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
// 线性素数筛选  prime[0]存的是素数的个数  
const int maxn = 1000000 + 5;  
int prime[maxn];  
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}  
int main() {  
    getPrime();//先进行素数筛选预处理  
    int n;  
    while (scanf("%d", &n) != EOF) {  
        int ans = 0;  
        for (int i = 1; i <= prime[0]; i++) {  
            while (n % prime[i] == 0) {  
                n /= prime[i];  
                ans++;  
            }  
        }  
        if (n > 1) ans++;  
        printf("%d\n", ans);  
    }  
    return 0;  
}  

练习题目

DreamJudge 1284 整除问题