一种比较简便理解为什么j 循环到i%Prime[j]= 0就恰好需要停止的证明
查看原帖
一种比较简便理解为什么j 循环到i%Prime[j]= 0就恰好需要停止的证明
803885
_8008008楼主2024/9/29 14:09

可能会有点问题,请大佬们指正

primeiprime_i 指第 ii 个质数

因为 imodprimej1=0i \bmod prime_{j-1}=0

一定有 pp 满足 p×pj1=ip\times p_{j-1}=ip1p\neq1

设合数 s=i×primejs=i\times prime_j

s=p×primej1×primejs=p\times prime_{j-1}\times prime_j

这样不满足最小质因数×最大因数=这个合数的筛法

2024/9/29 14:09
加载中...