求質數的各種算法

首先聲明本人水平有限，僅僅做一下記錄，有錯的地方請指正，文章垃圾請包容！！

在網上不小心瀏覽到一篇技術博客，叫做《求質數算法的N種境界（N>10）》，寫得很好，有興趣的讀者自己去搜索。然后就想自己去試試這篇博客里寫得各種求質數的方法。

不想搭環境，就暫時用了PHP語言，在apache里運行，簡易測試一下。

首先明確一下概念

質數（prime number）又稱素數，有無限個。質數定義為在大于1的自然數中，

除了1和它本身以外不再有其他因數的數稱為質數。

100以內質數表

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

53 59 61 67 71 73 79 83 89 97

質數的個數是無窮的。

相對的就是合數

合數，數學用語，英文名為Composite number，指自然數中除了能被1和本身整除外，

還能被其他數（0除外）整除的數（如：4，6，8，9，10）。

與之相對的是質數，而1既不屬于質數也不屬于合數。最小的合數是4。

以下是求100以內的質數算法

//1.最基礎的寫法

$a = 1;//序號，標識個數

for($i = 2; $i < 101; $i++) {

$primes = 0;

for($k = 1; $k <= $i; $k++)

if($i%$k === 0) $primes++;

if($primes <= 2){ // 能除以1和自身的整數(不包括0)

echo $a . ".{$i}

";

$a++;

}

}

//2.考慮所有數都可以被1整除和

//如果有（除了自身以外的）質因數，那肯定會小于等于 $i/2，所以 $i/2

//這里不能輕易將第一個算法的語句for($k = 1; $k <= $i; $k++)改成

//for($k = 1; $k <= $i/2; $k++); 原因自己試試就知道了

$a = 1;//序號，標識個數

for($i = 2; $i < 101; $i++) {

$primes = 0;

for($k = 2; $k <= $i/2; $k++)

if($i%$k === 0) $primes++;

if($primes <= 0){ // 能除以1和自身的整數(不包括0)

echo $a . ".{$i}

";

$a++;

}

}

//3.進一步想除了2以外，所有可能的質因數都是奇數。

//所以先測試2，然后再測試3到$i/2的所有奇數。

//關鍵特殊考慮數字2

$a = 1;//序號，標識個數

for($i = 2; $i < 101; $i++) {

$primes = 0;

if($i != 2 && $i%2 === 0) $primes++;

for($k = 3; $k <= $i/2; $k=$k+2) if($i%$k === 0) $primes++;

if($primes <= 0){ // 能除以1和自身的整數(不包括0)

echo $a . ".{$i}

";

$a++;

}

}

//4.其實只要從 2 一直嘗試到√x（開平方），就可以了。

$a = 1;//序號，標識個數

for($i = 2; $i < 101; $i++) {

$primes = 0;

if($i != 2 && $i%2 === 0) $primes++;

for($k = 3; $k <= sqrt($i); $k=$k+2) if($i%$k === 0) $primes++;

if($primes <= 0){ // 能除以1和自身的整數(不包括0)

echo $a . ".{$i}

";

$a++;

}

}

//5.其實只要從 2 一直嘗試到√x（開平方）其中的所有質數就可以

//算法理論中經常提到的：以空間換時間。就是先存之前的結果再拿來用

//以下本人寫得只是用一個數組來實現這個算法，本人技術有限，不知這樣是否準確理解原博

//客作者的意圖，就當隨便看看吧

$arr =array();

$a = 1;//序號，標識個數

for($i = 2; $i < 101; $i++) {

$primes = 0;

if($i != 2 && $i%2 === 0) $primes++;

if(!empty($arr)){

foreach($arr as $key => $value){

    if($value <= sqrt($i)){

        if($i%$value === 0) $primes++;

    }

}

}

if($primes <= 0){ // 能除以1和自身的整數(不包括0)

array_push($arr,$i);

echo $a . ".{$i}

";

$a++;

}

}

接下來，我們做一下簡單的性能測試，比較一下各個算法的優劣，僅僅從時間上考慮以下是測試結果

因為算法1，2,3差異性不是很大，不做比較，比較以下1,4,5的優劣

100以內

算法一

[time:0.0009×××752075195]s

算法五

[time:0.0010001659393311]s

結果顯示在100以內差異性不大

1000以內

算法一

[time:0.059004068374634]s

算法四

[time:0.004000186920166]s

算法五

[time:0.035001993179321]s

結果顯示在1000以內，算法四已經凸顯優勢了

10000以內

算法一

[time:4.537260055542]s

算法四

[time:0.19901204109192]s

算法五

[time:1.9741129875183]s

結果顯示在10000以內，算法一已經不行了

算法五也不行了

100000以內

算法一

[time:542.75104403496]s

算法四

[time:3.6972119808197]s

算法五

[time:164.25539493561]s

結果顯示在100000以內，除了算法四可行，其他都不行

總結：開始以為算法五會更勝一籌，不知道是我寫法垃圾，還是php數組的底層問題，也可能我不理解空間換時間的本質，所以目前還是算法4最優了。

本人水平有限，僅僅做一下記錄，有錯的地方請指正，文章垃圾請包容！！