当需要将 \(N!\) 分解为质因数的乘积时，直接计算阶乘再分解显然不现实，因为 \(N\) 稍大时结果就会巨大无比。勒让德公式提供了一种优雅的方法，可以直接计算出 \(N!\) 中每个质因子的指数，而不需要计算阶乘本身。

勒让德公式：对于任意质数 \(p\)，阶乘 \(N!\) 中质因子 \(p\) 的指数 \(v_p(N!)\) 等于 \(v_p(N!) = \left\lfloor \dfrac{N}{p} \right\rfloor + \left\lfloor \dfrac{N}{p^2} \right\rfloor + \left\lfloor \dfrac{N}{p^3} \right\rfloor + \cdots = \sum \limits_{k=1}^{\infty} \left\lfloor \dfrac{N}{p^k} \right\rfloor\)，这里 \(\lfloor x \rfloor\) 表示向下取整。

为什么这个公式成立？考虑从 \(1\) 到 \(N\) 的所有整数，每个数都可能贡献若干个质因子 \(p\)，逐层计算：

• 首先，在 \(1, 2, \dots, N\) 中，能被 \(p\) 整除的数有 \(\lfloor N/p \rfloor\) 个，每个这样的数至少贡献一个 \(p\)。
• 其次，在这些数中，有些数还能被 \(p^2\) 整除，它们会额外再贡献一个 \(p\)（因为已经算过一次，所以第二次相当于补上一个 \(p\)），能被 \(p^2\) 整除的数有 \(\lfloor N/p^2 \rfloor\) 个。
• 以此类推，能被 \(p^k\) 整除的数有 \(\lfloor N/p^k \rfloor\) 个，每个这样的数贡献了第 \(k\) 个 \(p\)。

因此，总指数就是所有 \(k\) 的 \(\lfloor N/p^k \rfloor\) 之和。当 \(p^k \gt N\) 时，\(\lfloor N/p^k \rfloor = 0\)，所以实际上只需计算到 \(p^k \le N\) 为止。

例题：P10495 阶乘分解

给定整数 \(N \ (3 \le N \le 10^6)\)，要求将 \(N!\) 分解质因数，并按照算术基本定理的形式输出所有质因子 \(p_i\) 及其指数 \(c_i\)。

只有 \(\le N\) 的质数才可能是 \(N!\) 的质因子，使用线性筛筛出所有可能的质因子。

对于筛出的每个质数 \(p_i\)，应用勒让德公式计算其指数。

线性筛部分的时间复杂度为 \(O(N)\)，而 \(N\) 以内质数个数约为 \(O(N/ \log N)\) 个，对于每个质数，只需要 \(O(\log N)\) 的时间计算，因此对整个 \(N!\) 分解质因数的时间复杂度为 \(O(N)\)。

#include <cstdio>
const int N = 1e6 + 5;
bool f[N];
int p[N], cnt;
void sieve(int n) {
    f[0] = f[1] = true;
    cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            p[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * p[j] <= n; j++) {
            f[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
}
int main()
{
    int n; scanf("%d", &n);
    sieve(n);
    for (int i = 0; i < cnt; i++) {
        int c = 0, t = p[i];
        // 使用循环累加每个 p^k 的倍数个数
        while (t <= n) {
            c += n / t;
            if (n / p[i] < t) break; // 防止溢出
            t *= p[i];
        }
        printf("%d %d\n", p[i], c);
    }
    return 0;
}