当需要将 \(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 \rt 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;
}