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

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

計算機(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)国夜，所以它們一定不是素數(shù)，再除去6x本身短绸，顯然车吹，素數(shù)要出現(xiàn)只可能出現(xiàn)在6x的相鄰兩側(cè)。這里有個題外話鸠按，關(guān)于孿生素數(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