轉(zhuǎn)自：判斷一個數(shù)是否為質(zhì)數(shù)/素?cái)?shù)——從普通判斷算法到高效判斷算法思路_C/C++_huang_miao_xin的博客-CSDN博客

定義：約數(shù)只有1和本身的整數(shù)稱為質(zhì)數(shù)，或稱素?cái)?shù)。

計(jì)算機(jī)或者相關(guān)專業(yè)，基本上大一新生開始學(xué)編程都會接觸的一個問題就是判斷質(zhì)數(shù)，下面分享幾個判斷方法，從普通到高效。

1）直觀判斷法最直觀的方法，根據(jù)定義，因?yàn)橘|(zhì)數(shù)除了1和本身之外沒有其他約數(shù)，所以判斷n是否為質(zhì)數(shù)，根據(jù)定義直接判斷從2到n-1是否存在n的約數(shù)即可。C++代碼如下：

bool isPrime_1( int num )

{? ? int tmp =num- 1; ??

?for(int i= 2;i <=tmp; i++) ? ? ?

? ? if(num %i== 0) ? ? ? ?

? ? ? ? return 0 ; ? ?

return 1 ;}

2）直觀判斷法改進(jìn)上述判斷方法，明顯存在效率極低的問題。對于每個數(shù)n，其實(shí)并不需要從2判斷到n-1，我們知道，一個數(shù)若可以進(jìn)行因數(shù)分解，那么分解時得到的兩個數(shù)一定是一個小于等于sqrt(n)，一個大于等于sqrt(n)，據(jù)此，上述代碼中并不需要遍歷到n-1，遍歷到sqrt(n)即可，因?yàn)槿魋qrt(n)左側(cè)找不到約數(shù)，那么右側(cè)也一定找不到約數(shù)。

C++代碼如下：

bool isPrime_2( int num )

{? ? int tmp =sqrt( num); ??

?for(int i= 2;i <=tmp; i++) ? ? ? ?

if(num %i== 0) ? ? ??

?? return 0 ; ??

?return 1 ;}

3）另一種方法方法（2）應(yīng)該是最常見的判斷算法了，時間復(fù)雜度O(sqrt(n))，速度上比方法（1）的O(n)快得多。最近在網(wǎng)上偶然看到另一種更高效的方法，暫且稱為方法（3）吧，由于找不到原始的出處，這里就不貼出鏈接了，如果有原創(chuàng)者看到，煩請聯(lián)系我，必定補(bǔ)上版權(quán)引用。下面講一下這種更快速的判斷方法；首先看一個關(guān)于質(zhì)數(shù)分布的規(guī)律：大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰。例如5和7，11和13,17和19等等；證明：令x≥1，將大于等于5的自然數(shù)表示如下：······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······可以看到，不在6的倍數(shù)兩側(cè)，即6x兩側(cè)的數(shù)為6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素?cái)?shù)，再除去6x本身，顯然，素?cái)?shù)要出現(xiàn)只可能出現(xiàn)在6x的相鄰兩側(cè)。這里有個題外話，關(guān)于孿生素?cái)?shù)，有興趣的道友可以再另行了解一下，由于與我們主題無關(guān)，暫且跳過。這里要注意的一點(diǎn)是，在6的倍數(shù)相鄰兩側(cè)并不是一定就是質(zhì)數(shù)。此時判斷質(zhì)數(shù)可以6個為單元快進(jìn)，即將方法（2）循環(huán)中i++步長加大為6，加快判斷速度，原因是，假如要判定的數(shù)為n，則n必定是6x-1或6x+1的形式，對于循環(huán)中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，則n至少得是一個偶數(shù)，但是6x-1或6x+1的形式明顯是一個奇數(shù)，故不成立；另外，如果n能被6i+3整除，則n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。綜上，循環(huán)中只需要考慮6i-1和6i+1的情況，即循環(huán)的步長可以定為6，每次判斷循環(huán)變量k和k+2的情況即可，理論上講整體速度應(yīng)該會是方法（2）的3倍。

代碼如下：bool isPrime_3( int num ){? ? ? ? ? ? ? ? //兩個較小數(shù)另外處理? ? ? ? ? ? ? ? if(num ==2|| num==3 )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return 1 ;? ? ? ? ? ? ? ? //不在6的倍數(shù)兩側(cè)的一定不是質(zhì)數(shù)? ? ? ? ? ? ? ? if(num %6!= 1&&num %6!= 5)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return 0 ;? ? ? ? ? ? ? ? int tmp =sqrt( num);? ? ? ? ? ? ? ? //在6的倍數(shù)兩側(cè)的也可能不是質(zhì)數(shù)? ? ? ? ? ? ? ? for(int i= 5;i <=tmp; i+=6 )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if(num %i== 0||num %(i+ 2)==0 )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return 0 ;? ? ? ? ? ? ? ? //排除所有，剩余的是質(zhì)數(shù)? ? ? ? ? ? ? ? return 1 ;}算法性能測試：編寫測試代碼，使用較多數(shù)據(jù)測試比較幾種方法的判斷效率，數(shù)據(jù)量40w，代碼如下：#include <iostream>#include <string>#include <ctime>#include <vector>using namespace std;bool isPrime_1( int num );bool isPrime_2( int num );bool isPrime_3( int num );int main(){? ? ? ? ? ? ? ? int test_num =400000;? ? ? ? ? ? ? ? int tstart ,tstop; //分別記錄起始和結(jié)束時間? ? ? ? ? ? ? ? //測試第一個判斷質(zhì)數(shù)函數(shù)? ? ? ? ? ? ? ? tstart=clock ();? ? ? ? ? ? ? ? for(int i= 1;i <=test_num; i++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? isPrime_1(i );? ? ? ? ? ? ? ? tstop=clock ();? ? ? ? ? ? ? ? cout<<"方法(1)時間(ms):" <<tstop- tstart<<endl ;//ms為單位? ? ? ? ? ? ? ? //測試第二個判斷質(zhì)數(shù)函數(shù)? ? ? ? ? ? ? ? tstart=clock ();? ? ? ? ? ? ? ? for(int i= 1;i <=test_num; i++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? isPrime_2(i );? ? ? ? ? ? ? ? tstop=clock ();? ? ? ? ? ? ? ? cout<<"方法(2)時間(ms):" <<tstop- tstart<<endl ;? ? ? ? ? ? ? ? //測試第三個判斷質(zhì)數(shù)函數(shù)? ? ? ? ? ? ? ? tstart=clock ();? ? ? ? ? ? ? ? for(int i= 1;i <=test_num; i++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? isPrime_3(i );? ? ? ? ? ? ? ? tstop=clock ();? ? ? ? ? ? ? ? cout<<"方法(3)時間(ms):" <<tstop- tstart<<endl ;? ? ? ? ? ? ? ? cout<<endl ;? ? ? ? ? ? ? ? system("pause" );? ? ? ? ? ? ? ? return 0 ;}

————————————————

版權(quán)聲明：本文為CSDN博主「huang_miao_xin」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/huang_miao_xin/article/details/51331710