埃氏筛详细讲解

由于暴力枚举可能会TLE（时间超限），所以我们可以定义一个埃氏筛函数筛选质数

#include<bits/stdc++.h>//使用埃氏筛优化
using namespace std;
bool prime[20010];//prime[i]=0表示i是质数，=1表示i不是质数
void check(){//筛查20010以内的质数
    prime[0]=1;//0和1绝对不是质数，直接筛掉
    prime[1]=1;
    for(int i=2;i<=20010;i++){
        if(prime[i]==0){//如果i是质数，就把所有i的倍数筛掉
            for(int j=i*i;j<=20010;j+=i){
                prime[j]=1;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    check();//筛选质数
    for(int i=2;i<=n;i++){//如果i是质数就输出
        if(prime[i]==0)cout<<i<<" ";
    }
}