洛谷 P3383 线性筛素数

链接：https://www.luogu.org/problemnew/show/P3383

思路：模板题，直接上欧筛即可，要注意的是本题要求是输入一个，判断一个，所以额外加一个ans数组

代码：

 1 //#include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<vector>
 4 #include<stack>
 5 #include<string>
 6 #include<cstdio>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<map>
10 #include<set>
11 #include<cmath>
12 #define inf 0x3f3f3f3f
13 using namespace std;
14 typedef long long ll;
15 const int MAXN = int(1e7) * 2 + 5;
16 int prime[MAXN];
17 bool vis[MAXN];
18 bool ans[MAXN];
19 int cnt = 0;
20 void Euler_peime(int n)
21 {
22     for (int i = 2; i <= n; ++i)
23     {
24         if (!vis[i])
25         {
26             prime[cnt++] = i;
27             ans[i] = true;
28             vis[i] = true;
29         }//vis[i]置为true或不置true都可以
30         for (int j = 0; j < cnt; ++j)
31         {
32             if (i*prime[j] > n)//判断是否越界
33                 break;
34             vis[i*prime[j]] = true;//筛数
35             if (i%prime[j] == 0)//时间复杂度为O(n)的关键！
36                 break;
37         }
38     }
39 }
40 signed main()
41 {
42     int n, m;
43     cin >> n >> m;
44     Euler_peime(n);
45     for (int i = 0; i < m; i++)
46     {
47         int x; cin >> x;
48         if (ans[x] == true) cout << "Yes" << endl;
49         else cout << "No" << endl;
50     }
51     return 0;
52 }

备注：欧拉筛法之所以是线性的，就在于他不会重复筛掉某些数，就是一种优化的埃筛，详情可见这篇博客

————————————————
心里有光，哪儿都美