埃氏篩法

int main() {const int maxNumber=200;int isPrime[maxNumber];int i;int x;for (i=0;i<maxNumber;i++){isPrime[i]=1;}for (x=2;x<maxNumber;x++){if (isPrime[x]){for (i=2;i*x<maxNumber;i++){isPrime[i*x]=0;}}}for (i=2;i<maxNumber;i++){if (isPrime[i]){printf("%d\t",i);}}printf("\n");return 0; }

首先初始化零和一，然后是整個數組，全部初始化為一，表示目前都是素數。

然后開始篩選，從二開始，如果判斷數組里面為一，說明這個數是素數，第一個進去的是二，二自然是素數，然后第一遍篩去二的所有倍數，然后再進入三，篩去三的所有倍數。

對于四來說，它在標記數組里面的值已經是零了，所以無法進入，也就不再篩去，篩過一遍之后便不再篩除，節省時間。

但是這也只是相對的，比如歐拉篩法。

歐拉篩法

#include <cstdio> #include <cstring> const int max=50000; int prime[20000]; bool vis[max]; int main() {int cnt=0;memset(vis,0,sizeof(vis));memset(prime,0,sizeof(prime));for (int i=2;i<max;i++) {if (!vis[i])prime[cnt++]=i;for (int j=0;i*prime[j]<=max&&j<cnt;j++) {vis[i*prime[j]]=1;if (i%prime[j]==0)break;}}for (int i=0;i<100;i++)printf("%d ",prime[i]);return 0; }

這個篩法的意思實際上是一個合數是由兩個數相乘所得，當這個是素數，就篩到它的平方的時候就不再讓它篩下去了，因為它后面還有其它的數可以去篩選。

而篩選的標準是從素數表里面從大到小選數與這個數相乘，這樣的話，當前的素數就會乘一遍比它小的素數，這樣也就將小素數的倍數也間接篩去了，就不需要小素數一直篩選，直接跳出即可。

如果不是素數，就篩選到它的最小質因子，這樣既是篩掉小素數的倍數，也相當于是篩掉了后面略大的素數的倍數。

轉載于:https://www.cnblogs.com/xyqxyq/p/10211385.html

總結

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

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