勒讓德定理（階乘中含有某質因子的數目）
[編輯] [转简体] （简体译文）概要
勒讓德定理指的是在正整數 a 的素因子分解中，素數 p 的指數爲 r(a)，那麼
r(n!) = [n/p]+[n/p^2]+[n/p^3]+...
正文
Legendre 定理（勒讓德定理）
指的是在正整數 a 的素因子分解中，素數 p 的指數爲 r(a)，那麼 （也就是 a 裏面最多可以分解出多少個素因子 p）
r(n!) = [n/p]+[n/p^2]+[n/p^3]+...
應用
求一個階乘裏面含某質因子 p 的數目，非常實用
證明：
因爲
r(n!)=r(1)+r(2)+...+r(n)
因爲 p 是素數，不可能由兩個大於 1 的數相乘得到，所以求 r(n!) 可以將 n! 拆解爲 1*2*3*...*(n-1)*n，累計每一塊裏面可以分解出多少個素數 p
相反，如果 p 是合數，那就不能這樣拆解，因爲需要考慮拆開的若干塊乘起來會不會構成新的合數 p
=r(p)+r(2p)+...+r([n/p]p)
因爲能使 r(x) 不爲 0 的 x 肯定是 p 的倍數，因此這裏只保留下來符合 r(x)（其中 x 爲 p 的倍數）形式的項
x 的最大值設爲 k*p <= n（k 爲正整數），則 k<=n/p 故 k=[n/p]
=(1+r(1)) + (1+(r(2)) + ... + (1+r([n/p]))
將 r(K*p) 分解爲 1+r(K)
=[n/p]+r(1)+r(2)+...+r([n/p])
=[n/p]+r([n/p]!)
成功構成遞推
所以
r([n/p]!) = [[n/p]/p]+r([[n/p]/p]!)
=[n/p^2]+r([n/p^2]!)
= ……
最後 r(n!) = [n/p]+[n/p^2]+[n/p^3]+...
或寫爲 r(n!) = [n/p]+[[n/p]/p]+[[[n/p]/p]/p]+...
代碼實現：
// 計算 n! 中質因子 p 的冪次
int CountPowerInFactorial(int n, int p)
{
int count = 0;
while (n)
{
n /= p;
count += n;
}
return count;
}參考資料：https://www.zhihu.com/question/38875219/answer/235385547