[模板]洛谷T3383 线性筛素数欧拉筛法

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<cstdlib>
 7 
 8 #include<string>
 9 #include<stack>
10 #include<queue>
11 #include<vector>
12 #include<algorithm>
13 #include<map>
14 #include<set>
15 
16 using namespace std;
17 
18 inline void read(int &x){
19     x=0;
20     char t=getchar();
21     bool f=0;
22     
23     while(t<'0' || t>'9'){
24         if(t=='-')f=1;
25         t=getchar();
26     }
27     
28     while(t>='0' && t<='9'){
29         x=(x<<3)+(x<<1)+t-'0';
30         t=getchar();
31     }
32     
33     if(f)x=-x;
34 }
35 
36 void Euler();
37 
38 bool pd[10000001];
39 int prime[700001],p=0;
40 
41 int n,m,i,j,x;
42 
43 int main(){
44     memset(pd,1,sizeof(pd));
45     
46     pd[1]=0;
47     
48     read(n);read(m);
49     
50     Euler();
51     
52     for(i=1;i<=m;i++){
53         read(x);
54         
55         if(pd[x])printf("Yes
");
56         else printf("No
");
57     }
58     
59     return 0;
60 }
61 
62 void Euler(){
63     int i,j;
64     
65     for(i=2;i<=n;i++){
66         if(pd[i]){
67             p++;
68             prime[p]=i;
69         }
70         
71         for(j=1;j<=p;j++){
72             if(i*prime[j]>n)break;
73             
74             pd[i*prime[j]]=0;
75             
76             if(i%prime[j]==0)break;
77         }
78     }
79 }
[模板]洛谷T3383 线性筛素数 欧拉筛法

[模板]洛谷T3383 线性筛素数欧拉筛法
