首页 > > 程序设计 > C/C++ >

【luogu 3383】【模板】线性筛素数

2018-06-17 21:48:01来源：未知阅读 ()

题目描述

如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数，即询问概数是否为质数。

输出格式：

输出包含M行，每行为Yes或No，即依次为每一个询问的结果。

输入输出样例

输入样例#1：

输出样例#1：

Yes
Yes
No
No
Yes

说明

时空限制：500ms 128M

数据规模：

对于30%的数据：N<=10000，M<=10000

对于100%的数据：N<=10000000，M<=100000

样例说明：

N=100，说明接下来的询问数均不大于100且大于1。

所以2、3、97为质数，4、91非质数。

故依次输出Yes、Yes、No、No、Yes。

普通筛法：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 bool is_prime(int x){
 7     if(x==1) return false;
 8     for(int i=2;i*i<=x;i++){
 9         if(x%i==0) return false;    
10     }
11     return true;
12 }
13 int n,m;
14 int main(){
15     scanf("%d%d",&n,&m);
16     for(int i=1;i<=m;i++){
17         int x;scanf("%d",&x);
18         if(is_prime(x)) puts("Yes");
19         else puts("No");
20     }
21     return 0;
22 }

埃式筛法：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath> 
 6 using namespace std;
 7 int n,m,q;bool is_prime[10000005];
 8 void eratos(int n){
 9     memset(is_prime,true,sizeof(is_prime));
10     is_prime[1]=false;
11     for(int i=2;i<=sqrt(n);i++){
12         if(is_prime[i]){
13             int j=i*2;
14             while(j<=n){
15                 is_prime[j]=false;
16                 j=j+i;
17             }
18         }
19     }
20 }
21 int main(){
22     scanf("%d%d",&n,&m);
23     eratos(n);
24     for(int i=1;i<=m;i++){
25         scanf("%d",&q);
26         if(is_prime[q]) printf("Yes\n");
27         else printf("No\n");
28     }
29     return 0;
30 }

欧式筛法（线性筛法）：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 bool is_prime[10000005];
 8 int prime[5000005],cnt=0,n,m,a; 
 9 void getlist(int n){
10     memset(is_prime,true,sizeof(is_prime));
11     is_prime[1]=false;
12     for(int i=2;i<=n/2;i++){
13         if(is_prime[i])prime[++cnt]=i;
14         for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
15             is_prime[i*prime[j]]=false;
16             if(i%prime[j]==0) break;
17         }
18     }
19 }
20 int main(){
21     scanf("%d%d",&n,&m);
22     getlist(n);
23     for(int i=1;i<=m;i++){
24         scanf("%d",&a);
25         if(is_prime[a]) printf("Yes\n");
26         else printf("No\n");
27     }
28     return 0;
29 }