昨天發出C語言經典算法（二）｜1-100之間有多少個素數之後，收到很多朋友的評論，讨論更高效的求素數的方法，我将大家的評論一一看過，覺得受益良多，同時也沒有閑着，動手又敲了一遍這些精妙的求素數的方法，發出來與大家共享。

這是一位大佬

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

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

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

什麼意思，就是最簡單的定義來就好了。根據定義，判斷一個整數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也不是。

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

确實我昨天的代碼錯了

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

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

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

來看一個關于質數分布的規律：大于等于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)，代碼可以這麼寫：

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

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

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!