程式設計實作素數的篩法

感覺自己寫得不太好 ，裡面還有不少問題。希望路過的大佬指點一二！！！！

直接進入主題，我們要解決的問題是 求1到n範圍内所有的素數。當然這個問題的難度取決n的大小。

兒童版 當n<=30的時候。（廢話）不用動手腦子裡面想一遍就知道有哪些素數了。

低級版 當 n<=60的時候。（廢話）這時就需要自己動手寫一下了。

初級版 當 n<=1e5的時候。（漸入佳境）手寫就有一點難受了，最好是依靠電腦程式設計求這些素數。而計算機的初學者就會想到利用素數的性質來判斷一個數是否是素數，及枚舉這個數所有可能的因子。

最初枚舉的時候枚舉的是2~n-1，發現這樣的枚舉方法有點笨，時間複雜度也有點高，O（n*n）。

然後自然而然的想到了有一半的數不用枚舉，隻需要枚舉2~n/2，時間複雜度也有點高，但畢竟除了一個2嘛，O（n*n/2）。

再後來想到一個合數最大的因子也不過是√n，那麼這個範圍又可以縮小。隻需要枚舉2~√n，在n比較小的時候這個時間複雜度是夠的。畢竟計算機每秒能跑1e9次，（見表1）O（n*√n）。

想想這個枚舉還可以優化，因為枚舉的時候枚舉了2，4，6，8，10…..，感覺4，6，8，10….這些東西是不用枚舉的，是以這個枚舉的的方法又一次得到了提高，（見表2）O（n*√n/2）。

int cnt=0;//素數的個數     for(int i=2;i<=n;i++)     {         int flag=0;//标記0 為素數          int xx=sqrt(i);         for(int j=2;j<=xx;j++)         {             if(i%j==0)             {                 flag=1;//标記1 能被整除不是素數                 break;             }         }         if(!flag)             b[++cnt]=i;//儲存這個素數 } 表 1

int cnt=0;//素數的個數     b[++cnt]=2;//先把存進去     for(int i=3;i<=n;i++)     {         int flag=0;//标記0 為素數         int xx=sqrt(i);         if(i%2==0)             continue;         for(int j=3;j<=xx;j+=2)//隻判斷奇數         {             if(i%j==0)             {                 flag=1;//标記1 能被整除不是素數                 break;             }         }         if(!flag)             b[++cnt]=i;//儲存這個素數 } 表 2

中級版，（慢慢進入重點）當 n<=（1e7~1e8） 時候O（n*√n/2）的時間複雜度漸漸變得很慢。這時候沒辦法，線性篩出現了。

線性篩的思想不難隻是不容易想到，首先标記所有的數都是素數，然後從2開始儲存目前被标記為素數的值，然後再把這個素數的倍數全都标記為合數。例如（見表3）把2存入素數裡面，再把2的倍數标記，把3存入素數裡面，把2的倍數标記，4被标記過了直接跳過，也不用标記4的倍數，把5存入素數裡面……以此類推。

1  2  3  4  5  6  7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 表3

這樣的時間複雜度比起O（n*√n/2）又上了一個台階，一個普通的線性篩就出來了。複雜度大約是（見表4）O（n*logn（longn））。

之是以說前面哪一個是普通的線性篩，那是因為這個也有可以優化的地方。例如，所有非2正偶數都不是素數，那麼隻需要把2特判一下，然後整個篩法不去篩偶數。還有就是每個素數篩掉的第一個數應該是i*i，因為比i小的合數都被比i小的質素篩掉了。（見表5）優化之後比起O（n*logn（longn））要好很多。感覺快要和O（n）接近了，時間複雜度小于O（n*logn（longn）/2）。

int cnt=0;//素數的個數     memset(vis,0,sizeof(vis));     for(int i=2;i<=n;i++)     {         if(!vis[i])         {             b[++cnt]=i;             for(int j=i+i;j<=n;j+=i)                 vis[j]=1;         } } 普通的線性篩 表4

int cnt=0;//素數的個數     b[++cnt]=2;//先把2存進去     memset(vis,0,sizeof(vis));     for(int i=3;i<=n;i+=2)//加2保證i是奇數     {         if(!vis[i])         {             b[++cnt]=i;             for(int j=i*i;j<=n;j+=(i+i))//加兩倍i保證j是奇數                 vis[j]=1;         } } 優化後的線性篩 表 5

進階版，（這很重點）當 n<=（1e9~1e10）線性篩的時間複雜度是達不到O（n）的。還得想跟好的辦法，告别了埃拉托色尼，了解一下歐拉（這個人是真的很恐怖，厲害！厲害！數論界的大佬，廢話就省略了……）。

歐拉篩的思想比線性篩要好，因為線性篩會把一個數篩多次，例如，135：3的倍數時候會篩一次，5的倍數也會篩一次。而歐拉篩就避免了這樣的問題，因為每個合數是由多個素數相乘而來，那麼就會有一個最小的素數，那這個合數就可以變成最小的這個素數乘上另一個數。那麼每個合數就隻會被篩到一遍。

歐拉篩法把時間時間複雜度降到了O（n）。同樣把大于2偶數排除掉。時間複雜度可以達到O（n/2）。那就直接來看O（n/2）的歐拉篩（見表6）

int cnt=0;//素數的個數     b[++cnt]=2;//先把2存進去     memset(vis,0,sizeof(vis));     for(int i=3; i<=n; i+=2) //加2保證i是奇數     {         if(!vis[i])         {             b[++cnt]=i;         }         for(int j=2; j<=cnt&&i*b[j]<=n; j++)         {             vis[i*b[j]]=1;             if(i%b[j]==0)                 break;         } } （n/2）歐拉篩 表 6

瘋狂版，當 n<=（1e11），超大範圍内素數的統計Meisell-Lehmer算法，1e11的範圍隻運作了2~3秒。（不會了…   逃）。

傳說版，隻是看見有人部落格上說 有一種DelegliseRivat的算法 1e16的範圍運作了3~4秒。（模版都沒有見過……   逃之夭夭）。