歐拉篩又稱線性篩，可以在線性的時間內篩出素數，因此在時間上要優于埃拉托斯特尼篩法。

歐拉篩是怎么做到在線性的時間內篩素數呢？先看代碼。

1 int n,vis[maxn],prime[maxn],cnt;
2     for(int i=2;i<=n;++i) {
3         if(!vis[i]) prime[++cnt]=i;
4     for(int j=1;j<=cnt&&i*prime[j]<=n;++j) {
5         vis[i*prime[j]]=1;
6         if(i%prime[j]==0) break; //這里是關鍵
7         }
8     }

不難看出，歐拉篩記錄了已篩出的素數，并用他們的整數倍找合數。而if(i%prime[j]==0) break;就是歐拉篩做到線性時間內篩素數的關鍵。我們假設當i%prime[j]==0時不跳出循環，接下來要被找到的合數是i*prime[j+1]，因為i能整除prime[j]，因此可以表示成k*prime[j]，這樣接下來的合數也可以寫成k*prime[j]*prime[j+1]，顯然prime[j]<prime[j+1]，說明至少有一個素數比prime[j+1]小，那他肯定不是這個合數的最小質因子，所以我們在此之前跳出循環，保證每個合數只會被他的最小質因子找到。比如12的質因子有2和3，12并不會在i=4時被3找到，而是會在i=6時被2找到。

轉載于:https://www.cnblogs.com/Mr94Kevin/p/9637899.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。