欧拉筛素数

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
bool isprime[10000000];
int prime[10000000];
//对于30%的数据：N<=10000，M<=10000
//对于100%的数据：N<=10000000，M<=100000
int main()
{
    cin>>n>>m;
    memset(isprime,true,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    int num=0;
    for(int i=2;i<=n;i++)
      {
        if(isprime[i])
          prime[++num]=i;
        //加入质数 
        for(int j=1;j<=num;j++)
          {
            if(i*prime[j]>n)
              break;
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)
              break; 
          }
      }
    int x;
    for(int i=1;i<=m;i++)
      {
        scanf("%d",&x);
        if(isprime[x])
          cout<<"Yes"<<endl;
        else
          cout<<"No"<<endl;
      }
} 

本作品采用《CC 协议》，转载必须注明作者和本文链接