P3383 【模板】线性筛素数
https://blog.csdn.net/huang_miao_xin/article/details/51331710
首先看一个关于质数分布的规律：
- 大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；
- 在6的倍数相邻两侧并不是一定就是质数。
证明：令x≥1，将大于等于5的自然数可表示成：[6x-1 6x 6x+1 6x+2 6x+3 6x+4]一组
其中6x 6x+2 6x+3 6x+4 可提出因子2或3，所以它们一定不是素数。
显然，素数要出现只可能出现在6x的相邻两侧。这里有个题外话，关于孪生素数，有兴趣的道友可以再另行了解一下，由于与我们主题无关，暂且跳过。
此时判断质数可以6个为单元快进，循环中i++步长加大为6，加快判断速度。
下面考虑如何对6x-1和6x+1进行判断？
现在n=6x-1或6x+1，找n有没有因子怎么找？
首先俩数都是奇数。因子不可能是2。
6x是3的倍数。6x+1和6x-1因子不能是3.
因子可能是：5、7 11、13 17、19 步长6。
这中间的数随便拿一个出来。都是2或3的倍数。
循环结束条件？判断到开根号就行了，这是判断质数的基本知识点。
代码：
1 |
License
Adopting CC BY-NC-SA 4.0 License Agreement
Share
