主要思路

欧拉筛的主要思想是每个合数只被他的最小质因子帅选一次,并且当一个数为素数时,他的倍数肯定不是素数

代码

#include<bits/stdc++.h>
const int N = 1e7;
bool isPrime[N+5];//判断对应的下标所代表的数字是不是素数 
int Prime[N+5];//保存每一个素数
int cnt = 0;//记录到第几个数字 
using namespace std;
//n代表一直到那个数 
void GetPrime(int n){
    memset(isPrime,1,sizeof(isPrime));//初始化默认所有数字都是素数
    isPrime[1] = 0;//1不是素数
    for(int i=2;i<=n;i++){
        if(isPrime[i]){
            //若i是素数
            Prime[++cnt] = i;//保存第cnt个素数    
        }
        for(int j=1;j<=cnt&&i*Prime[j]<=n;j++){
            //i*Prime[j]<=n防止超过范围 
            isPrime[i*Prime[j]] = 0;//是对应素数的合数均不是素数
            if(i%Prime[j]==0) break;
            //当 i % Prime[j]可以整除时,如果继续运算
            //i * Prime[j+1] = Prime[j] * k * Prime[j+1]
            //而 i是大于Prime[j],当 i = Prime[j] * k时
            //已经筛选过后面的数字,所以Prime[j+1]一定已经被筛过了
            //而Prime[j]必定是Prime[j]*i的最小质因子 
        } 
    }
}
int main(){
    //再范围n中选择m个数字判断是否是素数 
    int n,m;
    cin>>n>>m;
    GetPrime(n);
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(isPrime[a]==0){
            cout<<"No"<<endl;
        }
        else{
            cout<<"Yes"<<endl;
        }
    }
    return 0;
} 

一只小菜鸡