-数论- C++ 线性筛素数

在C++中，筛素数是一个非常重要算法。

我花了半天时间才明白的欧拉筛（我实在是太蒻了）。

最愚蠢的方法

#include<cstdio>
int main(){
    int n,k;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        if(n%i==0){
            printf("yes");
            return 0;
        }
    }
    printf("no");
}

普通方法

#include<cstdio>
int main(){
    int n,k;
    scanf("%d",&n);
    for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            printf("yes");
            return 0;
        }
    }
    printf("no");
}

以上两种方法其实都是判定方法，并不是筛法，下面说真正的筛法：

埃筛法

#include<iostream>
#define MAXN 1000010
using namespace std;
int chk[MAXN]={0};
int p[MAXN]={0};
int main(){
    int t=0;
    for (int i=2;i<MAXN;i++){
        if (!chk[i]) p[t++]=i;
        for (int j=0;j<t&& i*p[j]<MAXN;j++) {
            chk[i*p[j]] = 1;
        }
    }
}

思路：首先将所有2的倍数标为1，再将所有3的倍数标为1……以此类推。

欧拉筛

#define MAXN 1000000
int chk[MAXN]={0};
int p[MAXN]={0};
int main(){
    int t=0;
    for (int i=2;i<MAXN;i++){
        if (!chk[i]) p[t++]=i;
        for (int j=0;j<t&& i*p[j]<MAXN;j++) {
        	chk[i*p[j]] = 1;
            if (i%p[j]==0) break;
        }
    }
}

思路：由于埃筛法做了许多不必要的循环，所以欧拉筛在埃筛法的基础上，省去了一些步骤，时间复杂度O(n)。