欧拉筛法(线性素数筛)

时间:2019-03-09 14:23:08   收藏:0   阅读:2042
  1. 欧拉筛法的基本思想 :在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
  2. 理解:

 

技术分享图片

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

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!