欧拉筛（线性筛） & 洛谷 P3383 【模板】线性筛素数

嗯....

埃氏筛和欧拉筛的思想都是相似的：

如果一个数是素数，那么它的所有倍数都不是素数....

这里主要介绍一下欧拉筛的思路：（欧拉筛的复杂度大约在O(n)左右...

定义一个prime数组，这个数组被称为“素数表”，里面的数都为素数；然后用一个vis数组，如果一个数不是素数，则标记为1.

然后把i从2到n进行枚举，如果它没被访问过，则将其加入素数表中；然后for循环素数表，如果i % prime[j] == 0，则break即可，

**因为prime[j]作为i的一个质因数，在某一种情况下，它肯定会被筛过一次。并且注意要每次要判断i * prime[i] 是否大于n...**

下面这是一个模板题：

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

思路上面讲的已经很清晰了，下面是AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int n, m;
 7 int cnt;
 8 int prime[10000005], vis[10000005];
 9 
10 inline void is_prime(){
11     for(int i = 2; i <= n; i++){
12         if(!vis[i]) prime[++cnt] = i;
13         for(int j = 1; j <= cnt; j++){
14             if(i * prime[j] > n) break;//判断是否越界 
15             vis[i*prime[j]] = 1;//已访问 
16             if(i % prime[j] == 0) break;//欧拉筛核心 
17         }
18     }
19 }
20     
21 int main(){
22     scanf("%d%d", &n, &m);
23     is_prime();
24     vis[1] = vis[0] = 1;
25     int z;
26     for(int i = 1; i <= m; i++){
27         scanf("%d", &z);
28         if(vis[z]) printf("No
");
29         else printf("Yes
");
30     }
31     return 0;
32 }

AC代码