如何計算出質數?

以前見過有人問如何使用PHP算出質數。

今天剛好想到這個問題

小弟把它寫了一個簡單的例子,不過這樣算起來蠻花時間的

您如果想試試您電腦的計算能力

不妨再將$X=10000;設的更大
(這個值我的PC花了8秒左右,不知道還有沒有更快的計算方式?)


=======小範例開始============================
function getmicrotime(){
    list($usec, $sec) = explode(" ",microtime());
    return ((float)$usec + (float)$sec);
    }
//取得起始時間
$now = getmicrotime();

//設定質數範圍
$X=10000;

//取回來的放入陣列中
$XX=array();

for($i=1;$i<=$X;$i++){
    $chk=0;
    for($j=1;$j<=$i;$j++){
     if (($i%$j)==0) $chk++;
    }
     //如果是質數放入陣列中
    if ($chk==2) $XX[]=$i;
}

//取得結束時間
$now1 = getmicrotime();


echo count($XX)."個質數<br>";
echo "計算時間:".($now1-$now)."<br>";
echo join(', ',$XX);
標籤: PHP
評論: 2 | 引用: 0 | 閱讀: 9000
  • 1 
柏翰 [ 2016-03-14 10:16 網址 | 回覆 | 編輯/刪除 ]
我是柏翰
我是孩子王
我天下無敵
chian [ 2008-09-21 12:27 | 回覆 | 編輯/刪除 ]
以篩選法求質數,主要的方法是先篩去每個質數的所有倍數,剩下的就是質數了。求10000以下的質數,大約只需百分之1秒。

//篩選法求質數小程式:
<?php

//以篩選法求質數
//設定質數範圍
$n=10000;

$prime=array();
$sieve=array_fill(2,$n-1,1);

//需驗證次數
$verify = (int) sqrt((double) $n);

for ($i = 2; $i <= $verify;$i++) {
    if ($sieve[$i] == 0) continue;
    $k = $i + $i;    
    //每個質數的所有倍數均非質數
    while ($k <= $n) {     
        $sieve[$k] = 0;
        $k += $i;
    }
}

for($i=2;$i<$n;$i++)
    if($sieve[$i]) $prime[]=$i;

echo join(', ',$prime);     
    
?>
  • 1 
發表評論
暱 稱(*): 密 碼:
網 址: E - mail:
驗證碼(*): 驗證碼圖片 選 項:
頭 像:
內 容(*):
  • 粗體
  • 斜體
  • 底線
  • 插入圖片
  • 超連結
  • 電子郵件
  • 插入引用