[线筛|欧拉筛]线性筛选素数

来源：模板

题目描述：用线行筛筛选素数，将指定范围的素数找出，达到O（n）的效果。

思路

时间复杂度

0(n)

思路

任意值必然可以被分解为:​​a=b1^c1*b2*c2*...​​​ 例如​​9=3^3,15=3*5,55=5*11​​ 即所有的合数都可以被拆解为素数倍数的乘积。
当我们从2开始找到素数与含有素数的合数，将合数标记为​​非素数​​，每个合数都将被最小因素数标记，且只标记一次。
所以该公式虽然为双重循环，但实际时间复杂度为o(n);

注意 ​​if(i%primes[j]==0)break;​​

当这条命令执行时，有两种可能
1.被最小素数标记。
2.自己就是素数。
在第二种情况下往往会使合数遍历得很大，比如​​​i=7​​​遍历到​​49​​​才会停止，而​​35​​​就被​​7​​​标记，而非​​2​​。

CPP代码

#include<iostream>

using namespace std;

const int N=1e6+10;
bool st[N];
int primes[N],cnt;//prime质数，cnt计数当前值的位置

int get_primes(int n)
{
    for(int i=2;i<=n;i++)//最小素数是2，从2开始跑
        {
            if(!st[i])primes[cnt++]=i;//如果没有被判定，则表明是素数
            for(int j=0;primes[j]*i<=n;j++)//找出当前质数构成得合数,且该合数不得大于最大值n
                {
                    st[primes[j]*i]=true;//因为因数为素数，所以涉及合数标记为非素数
                    if(i%primes[j]==0)break;//保证当前值i可以被i得最小因素数标记，且只有一次，保证o(n)
                }
        }
}
int main()
{
    get_primes(1000);
    
    for(int i=0;i<20;i++)cout<<primes[i]<<endl;
    return 0;
}

以下解释来自博主​​__Simon_的文章欧拉线性筛素数
​

原理是利用了每个合数必有一个最小素因子,每个合数仅被它的最小素因子筛去正好一次，当 i 能整除 prime[ j ]，那么i * prime[ j+1 ] 这个合数肯定被 prime[j] 乘以某个数筛掉，因为 i 中有prime[j]且 i * prime[ j+1 ]中也有prime[ j ]。

举个例子：

当 i = 8，prime[ ] = 2,3,5,7；

i * prime[ ] = 16,24,40,56;

因为8 % 2 = 0，所以24，40，56,可以不筛，直接break;

就如上面那句话所说的，当8能整除2时，8乘以 下一个素数3 的值24，将会被12乘以2筛掉。

即24 = 8 * 3=(2 * 4) * 3 = 2 * (4 * 3) = 2 * 12; 被12筛掉

 40 = 8 * 5=(2 * 4) * 5 = 2 * (4 * 5) = 2 * 20; 被20筛掉

 56 = 8 * 7=(2 * 4) * 7 = 2 * (4 * 7) = 2 * 28; 被28筛掉

这些数后面会被筛掉，即 i = 12，20，28时。所以现在就不用筛选，降低时间复杂度。