【数论专题】—

【数论专题】——欧拉筛

上题：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 }

——抓住了时间，却不会利用的人，终究也逃不过失败的命运。