上题:https://www.luogu.org/problemnew/show/P3383
当你总是觉得筛质数太慢的时候,不妨来试一下欧拉筛:
基本原理:
设一个整数x,保证它只被它的最小质因子筛去。
具体请看代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e7+10; 4 bool check[N]; 5 int ans[N],cnt; 6 int m,k; 7 void Euler_sieve(int n){ 8 check[0]=check[1]=1; 9 for(int i=1;i<=n;i++){ 10 if(!check[i]) ans[++cnt]=i;//若未被筛去,说明是质数 11 for(int j=1;j<=cnt;j++){ 12 if(i*ans[j]>n) break;//i*ans[j] 13 check[i*ans[j]]=1;//标记号 14 if(i%ans[j]==0) break;//ans[j]保证只被筛去一次 15 } 16 } 17 } 18 int main(){ 19 cin>>m>>k; 20 Euler_sieve(m); 21 int r; 22 for(int i=1;i<=k;i++){ 23 cin>>r; 24 if(check[r]) cout<<"No"<<endl; 25 else cout<<"Yes"<<endl; 26 } 27 return 0; 28 }