0268 因子计数
* * * *
拉格朗日计划
* * * *
因子计数

可以验证,有23个小于1000的正整数能被至少四个小于100的不同质数整除。

求小于$10^16$的正整数中有多少个能被至少四个小于100的不同质数整除。

本题难度:



解答

不超过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)))