埃氏筛

约 94 个字 13 行代码

原理

素数的倍数一定不是素数，所以每找到一个素数，就把它的倍数标记

如果前面没标记当前数是合数，那么这个数就是素数

时间复杂度

$O(nlnlnn)$

缺陷

会重复筛一些数，比如$20=2*10=5*4$

用处

埃氏筛的思想会用到计算贡献上

例如洛谷p3601

代码

const int N=1e7+3;
bitset<N> v;//和int数组相比，空间小，速度快；比bool数组快
//v[i]为0表示i是素数，为1表示i不是素数
void Eratosthenes_seive()
{
    for(int i=2;i<N;++i)
    {
        if(v[i])
            continue;
        for(int j=i*i;j<N;j+=i)//i*i开始是为了减少重复筛
            v[j]=1;
    }
}