分析

• 阶乘的质因数分解：$n!$所有的质因子一定是小于等于n的，否则如果存在大于n的质因子，说明该质因子一定是某几个数相乘得到的，违反质数的定义。

（1）求出1~n中所有的质数，可以使用线性法筛质数；

（2）枚举某个质数p，则其在n!的质因数分解中出现的次数为：
$$ \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + ...... $$
该方法求阶乘$n!$的质因数分解的时间复杂度大约为$O(n)$，因为1~n中大约有$\frac{n}{log(n)}$个质数，求每个质数出现次数计算大约为$log(n)$的，相乘得到阶乘质因数分解时间复杂度大约为$O(n)$的。

• 另外指的一提的是：AcWing 888. 求组合数 IV这一题中就用到了阶乘的质因数分解。

代码

#include <iostream>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n) {

    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {

    int n;
    scanf("%d", &n);

    get_primes(n);

    for (int i = 0; i < cnt; i++) {
        int p = primes[i];

        int s = 0, t = n;
        while (t) s += t / p, t /= p;

        printf("%d %d\n", p, s);
    }

    return 0;
}