在傳統(tǒng)的素?cái)?shù)篩法中，我們使用了對(duì)于每一個(gè)數(shù)n，在 1~(√n) 范圍內(nèi)進(jìn)行取模檢查，這樣逐一判斷的復(fù)雜度為n(√n)。

但如果我們需要更快的篩法時(shí)怎么辦？

于是著名的歐拉篩誕生了。它能將復(fù)雜度降為**O(n)**級(jí)別。

1.關(guān)鍵理解：

歐拉篩的原理是保證在 2~n 范圍中的每一個(gè)合數(shù)都能被唯一分解成它的最小質(zhì)因數(shù)與除自己外最大的因數(shù)相乘的形式。因此我們枚舉2~n中的每一個(gè)數(shù)作為篩法中的“除自己外的最大因數(shù)”，如果它未被標(biāo)記為合數(shù)，就先將它放入素?cái)?shù)表內(nèi)，再將這個(gè)最大因數(shù)與素?cái)?shù)表中已經(jīng)找到的素?cái)?shù)作為最小質(zhì)因數(shù)相乘，將得到的這些數(shù)標(biāo)記為合數(shù)。最后輸出得到的素?cái)?shù)表即可。

但是我們?nèi)绾伪ＷC每個(gè)合數(shù)都被唯一分解？

解決方法如下：

當(dāng)此時(shí)取出的素?cái)?shù)表中的素?cái)?shù)(即枚舉的最小質(zhì)因子)整除于當(dāng)前枚舉的合數(shù)時(shí)，我們就停止循環(huán)素?cái)?shù)表，開(kāi)始枚舉下一個(gè)合數(shù)。

證明如下：

設(shè)當(dāng)前枚舉的最小質(zhì)因子prime[i]整除于合數(shù)n時(shí)，即我們要篩掉合數(shù) n*prime[i] ；如果我們此時(shí)不退出，繼續(xù)枚舉下一個(gè)素?cái)?shù)prime[i+1]，對(duì)于將要篩掉的合數(shù) n*prime[i+1] 由于插入順序從小到大，則 prime[i+1]>prime[i]。由于prime[i]整除于合數(shù)n，所以必然合數(shù) n*prime[i+1] 還可以被分解為

$$(\frac{n}{prime[i]}*prime[i+1])*prime[i]$$

顯然，在上面的分解方式中，我們將要篩掉的合數(shù)分解為更小的質(zhì)因子 prime[i] ，這不符合我們對(duì)于每一個(gè)數(shù)被唯一分解的要求，所以我們可在代碼中加入一行判斷整除關(guān)系的代碼進(jìn)行優(yōu)化。

2.代碼實(shí)現(xiàn)：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

inline void read(int &x){

x=0;int f=1;

char ch=getchar();

while(ch'9'){

if(ch=='-')

f=-1;

ch=getchar();

}

while(ch>='0'&&ch<='9'){

x=(x<<1)+(x<<3)+(ch^48);

ch=getchar();

}

x*=f;

}

bool IsPrime[100005];

int prime[50005];

int main(int argc, char const *argv[])

{

int n,top=1;

memset(IsPrime,1,sizeof(IsPrime));

read(n);

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

{

if(IsPrime[i])

prime[top]=i,top++;

for(int j=1;j

{

if(i*prime[j]>n)

break;

IsPrime[i*prime[j]]=0;

if(i%prime[j]==0)

break;

}

}

cout<

for(int i=1;i

cout<

return 0;

}

總結(jié)

以上是生活随笔為你收集整理的java 素数欧拉筛选_[C++]欧拉素数筛的理解与实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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