求質數的各個算法比較

QLQ 發布于2019-06-27 16:17 / 3613人閱讀

摘要：首先明確一下概念質數又稱素數，有無限個。質數定義為在大于的自然數中，除了和它本身以外不再有其他因數的數稱為質數。以內質數表質數的個數是無窮的。

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

在網上不小心瀏覽到一篇技術博客，叫做《求質數算法的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.00099992752075195]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最優了。

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

GPU云服務器云服務器最快比較排序算法字符串比較大小算法字符串比較最快算法字符串相似度比較算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/22822.html

電影里的代碼之《機械姬》：篩法求質數

摘要：影片處出現了一段代碼，細看了一下，發現是篩法求質數的代碼，寫得非常簡練的。重點還是前面的兩個函數實現的篩法求質數。今天看了《機械姬》，探討人工智能話題的電影，豆瓣評分7.5，還是蠻不錯的一部電影。影片1:09:29處出現了一段python代碼，細看了一下，發現是篩法求質數的python代碼，寫得非常簡練的。先貼個電影的截圖： showImg(https://segmentfault....

simon_chen 2019-07-24 18:19 評論0 收藏0
Dubbo 源碼分析 - 集群容錯之 LoadBalance

摘要：即服務提供者目前正在處理的請求數一個請求對應一條連接最少，表明該服務提供者效率高，單位時間內可處理更多的請求。此時應優先將請求分配給該服務提供者。初始情況下，所有服務提供者活躍數均為。 1.簡介 LoadBalance 中文意思為負載均衡，它的職責是將網絡請求，或者其他形式的負載均攤到不同的機器上。避免集群中部分服務器壓力過大，而另一些服務器比較空閑的情況。通過負載均衡，可以讓每臺服務...

ybak 2019-08-16 13:53 評論0 收藏0
算法之旅 | 選擇排序法

摘要：由于排序的算法有很多，在本次算法系列的分享當中，我們先從簡單易上手的選擇排序法開始，其它的排序算法會隨后陸續跟大家一起分享。 HTML5學堂-碼匠：數據快速的計算與排序，與前端頁面性能有直接的關系。由于排序的算法有很多，在本次算法系列的分享當中，我們先從簡單易上手的選擇排序法開始，其它的排序算法會隨后陸續跟大家一起分享。算法的基本概念算法是什么，它有何作用為解決一個問題而采取的方...

liaorio 2019-08-20 18:52 評論0 收藏0
OpenCV實戰 | 八種目標跟蹤算法

摘要：目標追蹤首先，我們會大致介紹八種建立在上的目標跟蹤算法。詞典包含了種的目標追蹤器行。它將目標追蹤器的命令行參數字符串映射到實際的追蹤器函數上。其中行里的目的是根據追蹤器命令行參數以及從得來的相關重要信息。雖然我們熟知的的質心追蹤器表現得很好，但它需要我們在輸入的視頻上的每一幀運行一個目標探測器。對大多數環境來說，在每幀上進行檢測非常耗費計算力。所以，我們想應用一種一次性的目標檢測方法，然后...

shevy 2019-04-25 18:29 評論0 收藏0