参考链接：https://oi.wiki/math/number-theory/factorial/#legendre-公式
在正整数 \(n!\) 的质因数分解中，质数 \(p\) 的指数（即 \(n!\) 能被 \(p\) 整除的最高次数，记为 \(v_p(n!)\)）可以通过以下公式计算：
\[v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor
\]
其中 \(\lfloor x \rfloor\) 表示向下取整（不超过 \(x\) 的最大整数）。因为当 \(p^k > n\) 时各项均为 0，所以这是一个有限项求和。
变体（进制表达）
Legendre 公式还可以写作
\[v_p(n!) = \frac{n - S_p(n)}{p - 1}
\]
其中 \(S_p(n)\) 是将 \(n\) 写成 \(p\) 进制时各位数字的和。
经典应用
常用于计算“\(100!\) 的末尾有几个零”（实际是求 \(v_5(100!)\) 的值）。
例题：洛谷P10495 阶乘分解
题目链接
示例程序（包含了上述两种 Legendre公式 的实现）：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 5;bool isp[maxn];
vector<int> primes;void init(int n) {for (int i = 2; i <= n; i++) {if (!isp[i]) {primes.push_back(i);}for (auto &j : primes) {if (i * j > n) break;isp[i * j] = true;if (i % j == 0) break;}}
}int n;int legendre_1(int n, int p) {int res = 0;for (ll t = p; t <= n; t *= p)res += n / t;return res;
}int s(int n, int p) {int res = 0;for (; n; n /= p)res += n % p;return res;
}int legendre_2(int n, int p) {return (n - s(n, p)) / (p - 1);
}int main() {scanf("%d", &n);init(n);for (auto &p : primes) {int ans = legendre_1(n, p);assert(ans == legendre_2(n, p));printf("%d %d\n", p, ans);}return 0;
}