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

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

新老客户大回馈,云服务器低至5折

题目描述

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:
100 5
2
3
4
91
97
输出样例#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 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU_5521_Meeting

下一篇:HDU_5517_Triple