欧拉筛（线性筛） & 洛谷 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代码：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int n, m;

 int cnt;

 int prime[], vis[];

 inline void is_prime(){

     for(int i = ; i <= n; i++){

         if(!vis[i]) prime[++cnt] = i;

         for(int j = ; j <= cnt; j++){

             if(i * prime[j] > n) break;//判断是否越界

             vis[i*prime[j]] = ;//已访问

             if(i % prime[j] == ) break;//欧拉筛核心

         }

     }

 }

 int main(){

     scanf("%d%d", &n, &m);

     is_prime();

     vis[] = vis[] = ;

     int z;

     for(int i = ; i <= m; i++){

         scanf("%d", &z);

         if(vis[z]) printf("No\n");

         else printf("Yes\n");

     }

     return ;

 }

AC代码

巴特西

欧拉筛（线性筛） & 洛谷 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代码：

最新文章

热门文章