【模板】线性筛素数(欧拉筛法)

题目

洛谷P3383线性筛素数

题解

筛法的本质是标记合数,即标记每个数的所有倍数。但在标记时,一个合数会被它的所有质因子重复标记多次,导致时间的浪费。因此,考虑让每个合数只被自己的最小质因数标记。

算法流程:用v[i]表示i的最小质因数,用不大于v[i]的所有质数p标记合数i*p,并更新v[i*p]=p。

1~n之间的素数个数约为

代码

Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月26日 上午9:44

(我昨天那么大一坨评论怎么不见了???)
【小白解析】
此题解法比较明晰:遍历每一个数字,考察其最小质因数;若该数字的最小质因数未被更新(即v[i]==0),说明该数不拥有之前任一质数作为因数,说明该数即是质数,存储在prime[]数组中。随后遍历当前所有的质数并计算其i倍,并更新v[i*当前质数]。
第10行循环中的i不仅表示每一个等待考察的数字,也表示对后续循环中prime[j]的倍数。更具体地讲,i的第二个作用保证了对于任何质数x,其不小于x*x的倍数的数字在v[]数组中,均被赋值x——也就是说为x的倍数声明其最小质因数。不难发现对于任何x>2,数组v[]中x*2~x*(x-1)的倍数均没有被考察——这是因为在之前的某步中,程序一定已为2*x~(x-1)*x赋值,故不需要再考察。(例:i==7时程序没有赋值7*2,但此情况下j==1时已考察过2*7。
第16行的判断包含两重信息:

  • 若当前使用的质数大于当前考察的v[i]——也就是说i并非质数(如果i是质数,i一定是最新被考察的,也即是当前最大的质数,v[i]==1,不会出现v[i]小于先前任一质数的情况。),则不必要考察剩余的情况——因为仅当v[i]和prime[j]均为质数,或者v[i]的最小质因数大于prime[j]时(参考上一段),i*prime[j]才是尚未被考察过的下标;

*该点我并不确定是否如此,请各位大神做进一步分析;

  • 若prime[j]*i大于总数范围n,则不需要考虑;、

综上即可得出所有需要的质数信息。

cyx
cyx
Reply to  cyx
2020年8月26日 上午9:52

附:一些关于素数理论的杂谈
该定理可在n较大时,筛选出要考察的最大质数的排名x,通过x/ln(x)*n进行范围限制(大概吧)。

解析1.png