欧拉筛法(线性素数筛)
时间:2019-03-09 14:23:08
收藏:0
阅读:2042
- 欧拉筛法的基本思想 :在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
-
理解:
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)