素數打表法

埃拉托斯特尼篩法雖然已經将時間複雜度降低到O(n*logn)，但是還是有不足之處。

因為6在i=2時就被标記了，而在i=3的時候又被标記了一次，是以還是有改進的空間。

const int N=1e6+5;
int cnt=0,prime[N],n;
int vis[N];
void get_prime()//打素數表 普通篩法
{
    memset(vis,0,sizeof(vis));//假設都是素數
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            for(int j=i+i;j<=n;j+=i)//倍數
                vis[j]=1;
        }
    }
}
           

線性篩法–歐拉篩法O(n）

const int N=1e6+5;
int cnt=0,prime[N],n;
int vis[N];
void get_prime()//打素數表 線性篩法
{
    memset(vis,0,sizeof(vis));//假設都是素數
    for(int i=2;i<=n;i++)//i是倍數
    {
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<=n;j++)//針對每個已得的素數
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)//倍數i判斷
                break;
        }
    }
}