线性筛模板

不大于n的所有素数共几个

#include
    
     int n;int prime[100000005];bool vis[100000005];int find(int n){    int cnt=0;    for(register int i=2;i<=n;i++){        if(!vis[i]) prime[++cnt]=i;        for(register int j=1;j<=cnt;j++){            if(prime[j]*i>n) break;             vis[prime[j]*i]=1;            if(!i%prime[j]) break;        }    }    return cnt;}int main(){    scanf("%d",&n);    printf("%d",find(n));    return 0;}
    

优化：

将所有偶数去掉

洛谷P3383

#include
    
     using namespace std;const int maxn=100000005;int n,m,cnt=1,a[maxn];bool b[maxn];int main(){    scanf("%d%d",&n,&m);    b[1]=1;    a[1]=2;    b[4]=1;    for(register int i=3;i<=n/2+1;i++){        if(i%2==0)            b[i*2]=1;        else{            a[++cnt]=i;            for(register int j=1;j<=cnt;j++){                if(i*a[j]>n)    break;                b[i*a[j]]=1;            }        }    }    for(int i=1;i<=m;i++){        int x;        scanf("%d",&x);        if(b[x])    printf("No\n");        else    printf("Yes\n");    }    return 0;}