素数筛

当遇到要求1~n之间的素数时,最纯的方法是$n^2$的,稍微聪明点的是$n√n$的。
遇到$10^6$或者更大的数据时就挂了。
所以我们需要学习素数筛,可以在接近线性的时间内筛出素数。

这里我只说(会)最好背的一种筛法,复杂度为$O(nloglogn)$

代码很简洁,四行。
其中book[i]表示i是否不是素数(book[i]为1时表示i不是素数)

那个j最好是long long,不然容易爆。还有i*i需要用long long进行运算,不然也容易爆。

这个筛(至少)可以过$10^7$的数据(亲测)。

它运用的思想:

把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。
——度娘

例题

【模板】线性筛素数 LUOGU - 3383
传送门= ̄ω ̄=

题解:模板题。
代码: