歐拉素數(shù)篩法：

首先：?? n=factor_max * p? 每一個合數(shù)可以表示成這樣

其中 factor_max為n的最大因數(shù)，p滿足

1、它是素數(shù)

2、它比factor_max的所有因數(shù)小

即p為n的最小素因數(shù)

?

證明：

假設(shè)p不是素數(shù)，那么p=p1*p2*……，其中pi為素數(shù)，那么factor就是不是最大因數(shù)

?

所以可以引出歐拉篩法

對于一個數(shù)，把他最為一個數(shù)的最大因子，顯然可以利用已有的素數(shù)，產(chǎn)生一些合數(shù)只有一種產(chǎn)生方法(只有一個factor_max)，

那么可以枚舉 i 判定prime[n]是不是最小素因數(shù)就可以保證枚舉的不多不少

?

根據(jù) prime[n] | i 來判定是否完全枚舉

prime[n]充當最小素因子，一旦被整除就break，后面沒有篩除的，說明i不是他們的最大因數(shù)。這樣就不會重復(fù)了。

?

1 #include<cstdio> 2 #include<cstring> 3 const int maxn=10000; 4 5 int prime[maxn+1]; 6 void getprime() { 7 memset(prime,0,sizeof(prime)); 8 for(int i=2;i<=maxn;i++) { 9 if(!prime[i]) prime[++prime[0]]=i; 10 for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++) { 11 prime[i*prime[j]]=1; 12 if(i%prime[j]==0) break; 13 } 14 } 15 } 16 17 int main() { 18 getprime(); 19 for(int i=1;i<=prime[0];i++) { 20 printf("%d\n",prime[i]); 21 } 22 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ACMerszl/p/9572987.html

總結(jié)

以上是生活随笔為你收集整理的欧拉素数筛选的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。