231. 二项式系数质因数分解(The prime factorisation of binomial coefficients)
二项式系数\(C_{10}^3=120\)，其质因数分解为\(120=2^3\times3\times5=2\times2\times2\times3\times5\)，则有:
$$ 2+2+2+3+5=14 $$因此\(C_{10}^3\)的质因数分解后各项的和为\(14\)，求\(C_{20000000}^{15000000}\)质因数分解后各项的和。
为了找到组合数 \(\binom{20,000,000}{15,000,000}\) 的质因数分解中各项的和，我们可以使用勒让德（Legendre）公式。公式说明：在 \(n!\) 的质因数分解中，质数 \(p\) 的指数为：
$$
\mathrm{v_p}(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor
$$
组合数定义如下：
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}
$$
因此，质数 \(p\) 在组合数 \(\binom{n}{k}\) 的质因数分解中的指数为：
$$
\mathrm{v_p}\left(\binom{n}{k}\right) = \mathrm{v_p}(n!) - \mathrm{v_p}(k!) - \mathrm{v_p}((n-k)!)
$$
我们可以使用这个公式计算 \(\binom{20,000,000}{15,000,000}\) 的质因数分解中各项的和，代码如下：
# time cost = 29.6s
from sympy import primerange
def legendre(n, p):
exponent = 0
while n > 0:
n //= p
exponent += n
return exponent
def main(n=2000_0000, k=1500_0000):
total_sum = 0
for p in primerange(1,n):
exponent = legendre(n, p) - legendre(k, p) - legendre(n - k, p)
total_sum += exponent * p
return total_sum
这段代码将计算组合数 \(\binom{20,000,000}{15,000,000}\) 的质因数分解中各项的和。时间复杂度主要取决于质数的生成和勒让德计算。埃拉托斯特尼筛选法的时间复杂度为 \(O(n \log \log n)\)，勒让德计算的复杂度为 \(O(n \log n)\)。空间复杂度为质数列表的 \(O(n)\)。