欧拉筛法(线性素数筛)

时间：2019-03-09 14:23:08 收藏：0 阅读：2043

欧拉筛法的基本思想：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
理解：

技术分享图片

Code:

 1 #include <cstdio>
 2 #define maxn 100000
 3 int s[maxn],prime[maxn],i,j,cnt; //初始化都是素数
 4 void Prime()
 5 {
 6     for(i = 2; i <= maxn; i++) {
 7         if(!s[i]) prime[++cnt] = i;// cnt,记录素数个数
 8         for(j = 1; j <= cnt && i*prime[j] <= maxn; j++){
 9             s[i*prime[j]] = 1;
10             if(i % prime[j] == 0) break;
11         }
12     }
13 }

原文：https://www.cnblogs.com/cgx249/p/10500426.html