【数的专题】——欧拉筛

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

 

上一篇:求质数算法


下一篇:Sieve of Eratosthenes algorithm