洛谷 P3383 【模板】线性筛素数-线性筛素数(欧拉筛素数)O(n)基础题贴个板子备忘

影者东升

P3383 【模板】线性筛素数
题目描述
如题，给定一个范围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 //线性筛法筛素数(欧拉筛法)
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<bitset>
 7 #include<cassert>
 8 #include<cctype>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 using namespace std;
21 typedef long long ll;
22 
23 const double PI=acos(-1.0);
24 const double eps=1e-6;
25 const ll mod=1e9+7;
26 const int inf=0x3f3f3f3f;
27 const int maxn=2e7+10;
28 const int maxm=100+10;
29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
30 
31 bitset<maxn> is_prime;
32 int p[maxn],h=0;
33 
34 void Prime(int n)
35 {
36   is_prime[0]=1;
37   is_prime[1]=1;
38   for(int i=2;i<=n;++i){
39     if(is_prime[i]==0)
40       p[++h]=i;
41     for(int j=1;j<=h&&p[j]*i<=n;++j){
42       is_prime[i*p[j]]=1;
43       if(i%p[j]==0)
44         break;
45     }
46   }
47 }
48 
49 int main()
50 {
51   int n,m;
52   scanf("%d%d",&n,&m);
53   Prime(n);
54   for(int i=1;i<=m;i++){
55     int x;
56     scanf("%d",&x);
57     if(is_prime[x])
58       printf("No\n");
59     else
60       printf("Yes\n");
61   }
62   return 0;
63 }

溜了。。。