質數能幫你賺錢？| 尋找質數的最高效演算法

05-16

質數，指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數。這個特性使得質數在許多領域排上獨特的用場，比如RSA加密演算法，其實更妙的是，質數還可以用來幫你掙錢：

電氣工程師Jonathan Pac找到第50個梅森數獲得了3萬美元獎金

人類發現史上最大梅森素數：Intel i5-6600連跑六天-梅森,素數,質數,i5-6600,處理器,Intel,-驅動之家?

news.mydrivers.com

那麼問題來了，如何高效地尋找尋找質數呢？

方法一：

要想知道x是不是質數，那就用它試著去除2~x-1，如果可以被整除，那就不是質數唄。

毫無疑問，這個演算法效率是低到人難以忍受的。稍微優化一下，我們可以得到方法二。

方法二：

第一個質數為2，那x只要是大於2的偶數就必然不是質數，這樣我們就能排除掉一半的數了。對於奇數x，用它試著去除3、5...~x-2，如果可以被整除，那就不是質數。

計算效率高了一些，但演算法複雜度本質上和第一種沒什麼區別，只是係數級的改進。

方法三：

稍微思考一下就會發現，其實質數是分解質因數時只能分解成1和本身的數，既然如此，那麼我們在試除的時候就沒有必要從3、5一直除到x-2了，只需要除比自身小的質數就可以了。

方法四：

再進一步思考就會發現，其實也沒必要去試除所有比自身小的質數，只要試除比不大於自身的平方根的質數就可以了。

為什麼？

假設x不是質數，那麼它必然是最少兩個質數的乘積，如果這兩個質因數不相等，那麼必然有一個質因數小於√x，如果兩個質因數相等，那麼這個質因數必然等於√x。

這樣一來，我們總算得到一個還比較靠譜的演算法了：

class Solution {public: vector<int> FindPrimes(int n) { if(n<=2)return vector<int>(); vector<int>prime(1,2); for(int i=3;i<n;i+=2){ bool flag=true; int lim=sqrt(i); for(int r=0;prime[r]<=lim&&r<(int)prime.size();r++){ if(0==i%prime[r]){ flag=false; break; } } if(flag)prime.push_back(i); } return prime; }};

輸入n，這個演算法就能幫你找出所有不大於n的質數了。

用這個演算法去解決LeetCode上的題 204. Count Primes

Count Primes?

leetcode.com

嗯，通過了。

但你以為這就是最好的演算法了嗎？當然不是

方法五：

https://zh.wikipedia.org/wiki/埃拉托斯特尼篩法?

zh.wikipedia.org

這個演算法的思路和上面的方法完全不一樣，之前的4個方法採取「嚴進寬出」策略，只有經過層層試除後才會被放入數組中，數組中的數字也都是質數，不必做進一步處理。而這個演算法，採用的「寬進嚴出」，一上來就把所有數字全部放入數組，然後一步一步篩選，最後留下來的數字才是質數，所以這方法方法被形象地稱為：篩法。

具體的過程一張動圖就一目了然：

具體的演算法實現如下：

#include <algorithm>//std::remove_if#include <numeric>//std::iotastd::vector<int> eratosthenes(int max){ std::vector<int> vi(max+1);//0, 1, 2, ..., max std::iota(vi.begin(), vi.end(), 0); if(max>=2){ int prime=2; while(prime*prime<=max){//2 to sqrt(max) for(size_t index=prime*2; index<vi.size(); index+=prime){ vi[index]=0;//Rule out this number. } for(prime++; prime*prime<=max; prime++){ if(vi[prime]>0){ break;//Jump to next non-zero.which is prime number. } } } } vi.erase(std::remove_if(vi.begin(), vi.end(), [](int i)->bool{ return i<=1; }), vi.end());//Remove all zeros and the one. return vi;}

不妨來做一個速度對比：

#include<iostream>#include <vector>#include <math.h>using namespace std;//方法四：vector<int> FindPrimes(int n) { if(n<=2)return vector<int>(); vector<int>prime(1,2); for(int i=3;i<n;i+=2){ bool flag=true; int lim=sqrt(i); for(int r=0;prime[r]<=lim&&r<(int)prime.size();r++){ if(0==i%prime[r]){ flag=false; break; } } if(flag)prime.push_back(i); } return prime;}//方法五：#include <algorithm>//std::remove_if#include <numeric>//std::iotastd::vector<int> eratosthenes(int max){ std::vector<int> vi(max+1);//0, 1, 2, ..., max std::iota(vi.begin(), vi.end(), 0); if(max>=2){ int prime=2; while(prime*prime<=max){//2 to sqrt(max) for(size_t index=prime*2; index<vi.size(); index+=prime){ vi[index]=0;//Rule out this number. } for(prime++; prime*prime<=max; prime++){ if(vi[prime]>0){ break;//Jump to next non-zero.which is prime } } } } vi.erase(std::remove_if(vi.begin(), vi.end(), [](int i)->bool{ return i<=1; }), vi.end());//Remove all zeros and the one. return vi;}int main(){ const int n=1<<10; cout<<"尋找"<<n<<"以內的所有質數"<<endl; clock_t st=clock(); eratosthenes(n); cout<<"方法5耗時："<<double(clock()-st)/1000<<"ms"<<endl; st=clock(); FindPrimes(n); cout<<"方法4耗時："<<double(clock()-st)/1000<<"ms"<<endl;}

測試一：

測試二：

測試三：

可以看出來，n較小的時候，方法4還比較佔上風，當n比較大的時候，篩法就把方法四甩得很遠了。

這個篩法其實仍有改進空間，比如初始化數組的時候，偶數就沒必要放進數組。使用的一些stl的演算法其實也可以手動實現一份以優化性能。

感興趣的朋友不妨動手實現一下~

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：