我在一次采访中被问到以下问题：
如何解决这个问题：（（3000000！）/（30！）^100000）%（任何素数）
我用蛮力为C程序编写了同样的代码，但我确信他没有预料到这一点。有什么解决办法的建议吗？
最佳答案
3000000! = 1*2*3*4*5*..*8*...*16*...*24*...*32*...40*...*64*...*3000000
我们能数一数结果中的2吗是的，2的每一个幂对它的每一个倍数贡献一个2。所以n的因式分解中的2s总数！isn/2 + n/4 + n/8 + n/16 + n/32 + ...其中/是整数除法，项大于0时求和：
fnf n f = -- number of `f` factors in `n!`
sum . takeWhile (>0) . tail . iterate (`div` f) $ n
（编写伪代码in Haskell）当
f*f < n时，将有多个条目要汇总。对于较大的fs，只有一个条目可以求和，即。n `div` f。因此
n!的因子分解被发现为factfact n = -- factorization of n! as [ (p,k) ... ] for n! = PROD p_i^k_i
let
(ps,qs) = span (\p-> p*p <= n) primes -- (before, after)
in
[(f, fnf n f) | f <- ps] ++
[(f, n `div` f) | f <- takeWhile (<= n) qs]
现在，30的因式分解！有10个因素：
> factfact 30
[(2,26),(3,14),(5,7),(7,4),(11,2),(13,2),(17,1),(19,1),(23,1),(29,1)]
它的第10万次幂就是它的每一个因子系数乘以10万当我们取3000000的因式分解时！，其216816项中的前几项是：
> factfact 3000000
[(2,2999990),(3,1499993),(5,749998),(7,499996),(11,299996),(13,249998),
(17,187497),(19,166665),(23,136361),(29,107142),(31,99998), ...
所以除法之后，当我们从第一个数中减去第二个数时，没有一个是缺少的，也没有一个是完全抵消的：
[(2,399990),(3,99993),(5,49998),(7,99996),(11,99996),(13,49998),
(17,87497),(19,66665),(23,36361),(29,7142),(31,99998), ...
所以对于小于3000000的素数，余数是0如果它更大，
p > 3000000然后，我们在上面找到的这个因子分解的模指数mod p和乘法modp必须被使用关于这些有很多答案，等等。当然，在生产代码中（对于非惰性编程语言），我们不会构建中间因子分解列表，而是逐个处理3000000以下的每个素数（对于惰性语言，不需要这样做）。