题解 | 筛法判断质数

#include <cstring>
#include <iostream>
#include <vector>
#define N 1000001
using namespace std;

bool p[N];

int main() {
    memset(p, true, sizeof(p));
    p[0]=p[1]=false;
    int t, n, x;
    for(int i=2;i<=1000;i++){
        if(p[i]){
            x=i*i;
            while(x<=N){
                p[x]=false;
                x+=i;
            }     
        }
    }
    cin>>t;
    while(t--){
        cin>>n;
        if(p[n]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}