昨天發出 之後，收到很多朋友的評論，討論更高效的求素數的方法，我將大家的評論一一看過，覺得受益良多，同時也沒有閒著，動手又敲了一遍這些精妙的求素數的方法，發出來與大家共享。

這是一位大佬

就像上面這位朋友所說，求素數的方法確實有很多：100以下隨便做，枚舉估驗特判開心就好，100000以下用6倍篩，1000000以下用埃氏篩，100萬以上直接歐拉篩，不優化40000000以內秒過，一個億以內的歐拉優化過……

我真被這簡潔明瞭的概括驚呆了。

那今天就按照這樣的順序講一下這些求素數的方法吧。

100以內：隨便做

什麼意思，就是最簡單的定義來就好了。根據定義，判斷一個整數n是否是素數，只需要去判斷在整數區間[2, n-1]之內，是否具有某個數m，使得n % m == 0。

我們把這種方法叫做樸素判斷素數算法或者試除法，代碼是這樣的：

事實上，這個算法是O(n)的，感覺是很快了，但是依舊無法滿足需求。

所以有一個算法是O(sqrt(n))的算法：

原理很巧妙，也僅僅是把代碼的i < n變成了i * i <= n而已，但是優化卻是極其高的。可能你會注意到，在上一份代碼裡面，我定義的n為int類型，而後面一份代碼，我卻定義成了long long，這是因為在1s內，上一份代碼能判斷出來的數量級為1e8，而後面一份代碼判斷出來的數量級卻幾乎可以達到1e16。而原因僅僅是因為a * b = c的話一旦a是c的約數，那麼b也是，如果a不是，那麼b也不是。

這裡要插播一條誠摯的感謝，昨天的文章裡出現了一個巨大的錯誤，被一個小可愛指出來了，如下：

確實我昨天的代碼錯了

犯這樣的錯誤讓我心痛不已！！！

以後一定痛定思痛，好好學習天天向上！

6倍篩：一個神奇的規律

個人覺得這個方法，是一個神奇的發現。

來看一個關於質數分佈的規律：大於等於5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等。

這個規律的正確性我們這裡就不證明了，大家有興趣可以去查查資料，或者等待大佬評論區解答。

好，那麼知道這個規律，此時判斷質數就可以6個為單元快進，即將前面的方法循環中i++步長加大為6，加快判斷速度，原因是，假如要判定的數為n，則n必定是6x-1或6x+1的形式，對於循環中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，則n至少得是一個偶數，但是6x-1或6x+1的形式明顯是一個奇數，故不成立；另外，如果n能被6i+3整除，則n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。

綜上，循環中只需要考慮6i-1和6i+1的情況，即循環的步長可以定為6，每次判斷循環變量k和k+2的情況即可，理論上講這種方法整體速度應該會是樸素判斷素數法的3倍。代碼如下：

埃氏篩選法（埃拉託斯特尼篩法）

埃氏篩選法對於篩選整數n以內的素數，算法是這麼描述的：先把素數2的倍數全部刪除，剩下的數第一個為3，再把素數3的倍數全部刪除，剩下的第一個數為5，再把素數5的倍數全部刪除······直到把n以內最後一個素數的倍數刪除完畢，得到n以內的所有素數。代碼可以這麼寫：

這就是下面這位小可愛的觀點：

線性篩選

觀察可以發現，上面的這種寫法有很多次重複計算，這樣顯然無法做到線性篩選，而另外一種寫法卻可以得到線性篩選，達到時間複雜度為O(n)，代碼可以這麼寫：

Meissel-Lehmer算法

這個算法可以說是黑科技級別的，它能夠在3s內求出1e11之內的素數個數，據說還有在300ms內求出1e11的個數的。

本菜鳥我，望而卻步啊，完全沒有研究過，所以原理和代碼大家就自行百度吧。