显然$n!$中因子$p$的数量就是
$$\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\ldots$$
因此先用筛法找出两千万以内的素数，再用上述公式依次计算$20000000!$，$15000000!$，$5000000!$中各因子之和。
结果是$7526965179680$。
target=20000000
d=[0]*target
n=2
while n < target:
for i in range(n*n,target,n):
d[i]=d[i]+1
n=n+1
while n < target and d[n]>0:
n=n+1
primeList=[k for k in range(2,target) if d[k]==0]
print "prime list generated"
def f(n,p):
m=p
s=0
while m<=n:
s+=n/m
m*=p
return p*s
print sum(f(20000000,p) for p in primeList)-sum(f(15000000,p) for p in primeList)-sum(f(5000000,p) for p in primeList)
|
