质数特殊筛选方法

埃氏法

时间复杂度为\(O(nloglogn)\)，没有欧拉筛法复杂度小
代码如下：

void prime()
{
    num[0] = num[1] = 1;//特判
    for (int i = 2; i < MAX; i++)
    {
        if (num[i])
            continue;
        for (int j = i * 2; j < MAX; j += i)//质数的倍数肯定不是素数
            num[j] = 1;
    }
}

欧拉筛法

时间复杂度为\(O(n)\)为线性阶，所以欧拉筛法也被称为线性筛

void Prime()//0为质数，1为非质数 
{
    for(int i=2;i<n;i++)
    {
        if(!visit[i])
        {
            prime[++prime[0]]=i;//将素数存储下来 
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<MAXN;j++)
        {
            visit[i*prime[j]]=1;//不是像埃氏法一样用i的倍数消去和数，而是通过所有记录的素数，当作要消去数的最小素因子来消去
            if(i%prime[j]==0)//解释看下面 
            {
                break;
            }
        }
    }
}

if(i%prime[j]==0)
{
    break;
}

如果没有break，当\(i\)是\(prime[j]\)的倍数时\(i=k*prime[j]\)，当\(j=j+1\)时\(i*prime[j+1]=k*prime[j]*prime[j+1]\)，因为欧拉筛法是通过一个最小质因子去筛选的，所以\(prime[j]*prime[j+1]\)会在后面重复计算。

比如当\(i=8,j=1,prime[j]=2\)，当\(j=j+1\)时\(i*prime[j+1]=8*3=2*4*3=2*12\)但这个在\(i=12\)时会计算，所以计算重复。

质数特殊筛选方法

原文：https://www.cnblogs.com/JMWan233/p/11140842.html