• 埃式筛

//埃式
const int N=10001;
int primes[N],cnt=0;
bool st[N];
void get_p(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=i+i;j<=n;j+=i){
                st[j]=true;
        }

    }
}

• 线性筛

const int N=10001;
int primes[N],cnt=0;
bool st[N];
void get_prime(int n) {
    for(int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}