素数筛的三种写法

素数筛

思路：利用桶排序将范围的数都先标记为1，然后通过计算素数的倍数把和数计算出来，然后将和数标记为0。
时间复杂度：n*lgn
优点：思路清晰，容易手写。
缺点：是三种写法里最慢的一种。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int prime[N];//prime数组储存：素数
bool b[N];//b数组用来标记哪些数字是素数，哪些是素数的倍数也就是和数；
void get_prime()
{
    int i,j,num=0;//num储存素数的个数
    memset(b,1,sizeof(b));
    b[0]=b[1]=0;//因为0和1都不是素数
    for(i=2; i<=N; i++)
    {
        if(b[i])prime[++num]=i;//保存素数
        for(j=2*i; j<=N; j+=i)//筛选和数
            b[j]=0;
    }
}

埃氏筛

思路：埃氏筛在素数筛的基础上做了一些改进，减少了一些重复运算。
时间复杂度：n*lg(lgn)
优点：思路清晰，容易手写。
缺点：不是最快的算法，仍然包含了重复计算。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int prime[N];//prime数组储存：素数
bool b[N];//b数组用来标记哪些数字是素数，哪些是素数的倍数也就是和数；
void get_prime()
{
    int i,j,num=0;//用来统计素数的个数
    memset(b,1,sizeof(b));
    b[0]=b[1]=0;//因为0和1都不是素数
    for(i=2; i<=N; i++)
    {
        if(b[i])
        {
            prime[++num]=i;//保存素数
            for(j=2*i; j<=N; j+=i)b[j]=0;//筛选和数
        }
    }
}

线性筛

思路：从2开始筛，每次去除和数的时候，只去除到这个和数的最小素数时退出，剩下的和数由其他的素数去筛，一次只前进有限的个数并不是前进到最大值，因此可以不出现重复运算。
优点：最快的筛法。
缺点：不太容易记忆。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int prime[N];//prime数组储存：素数
bool b[N];//b数组用来标记哪些数字是素数，哪些是素数的倍数也就是和数；
void get_prime()
{
    int i,j,num=0;//num表明素数的个数；
    memset(b,1,sizeof(b));
    b[0]=b[1]=1;
    for(i=2; i<=N; i++)
    {
        if(b[i])
        {
            prime[++num]=i;//保存素数
            for(j=1;j<=num&&prime[j]*i<=N;j++)//当前的j要小于当前的素数个数，素数的倍数也就是和数不能超过最大值。
            {
                b[prime[j]*i]=0;//筛选和数
                if(i%prime[j]==0)break;//筛选到和数的最小素数的时候退出，剩下的由其他的素数去筛。
            }
        }
    }
}
int main()
{
    get_prime();//最后在主函数中记得引用该函数否则不会打出素数表。
    return 0;
}