不超过100的素数共有25个,把这个集合记作P,那么用容斥原理易得
$$\sum_{k=4}^{25} (-1)^{k}\binom{k-1}{3}\sum_{p_1,\ldots,p_k\in P}\frac{N}{\prod_{j=1}^kp_j}=785478606870985.$$
注:以下为Python 3代码,因math.comb,math.prod都是Python 3中新增的函数。
import itertools,math
n=10**16
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
print(sum((1 if k%2==0 else -1)*math.comb(k-1,3)*sum(n//math.prod(c) for c in itertools.combinations(p,k)) for k in range(4,26)))
|