続々続 エラトステネスのふるい
賢い人のコードを拝借
倍数でカウントアップして計算量を減らす方法だけど、
rangeで偶数を削除して検索対象の配列を生成する方法と両立できなかったので、
PHPでエラトステネスの篩で素数判定をやってみる - 『素数』を数えて落ち着くんだ…
から、コードを拝借。( ´д)ﾋｿ(´д｀)ﾋｿ(д｀ )
最初に偶数は除外しません。
さらにrangeではなく、指定した数だけ指定した要素を生成するarray_fill()を使って、
keyで評価します。
偶数も素数か評価してますが、
・倍数かどうか評価する
・素数リストにいれる
・探索リストの先頭を削除する
の計算が不要になってます。
//エラトステネスのふるい
//倍数でカウントアップ、array_fill()
public function action_eratos3($max_num=100)
{
$primary = array();
//整数にキャスト
$max_num = (int)$max_num;
//1以上か？
if($max_num >=1)
{
//1は素数
$primary[] = 1;
//2以上か?
if($max_num >= 2)
{
$sqrt = sqrt($max_num);
// keyで配列を一気に作る
$search = array_fill(2, $max_num - 1, true);
// もっと単純に倍数を取り除くだけ
for ($i=2; $i<=$sqrt; $i++) {
if (isset($search[$i])) {
for ($j=$i*2; $j<=$max_num; $j+=$i) {
unset($search[$j]);
}
}
}
$primary = array_merge($primary,array_keys($search));
}
}
return implode(" ",$primary);
}
1万までの素数を出力させた実行時間は
5ms
速い！
速すぎて1万までだと比較しづらくなってきたので、
前作った奴を含めて5万までの素数を出力させて、今回のガッテンとします。
5万までの素数を出力
| 特徴 | 実行時間 | |
|---|---|---|
| action_all() | 偶数を含めて全部探索する | 12sec |
| action_odd() | 奇数だけ探索する | 6sec |
| action_eratos() | エラトステネスのふるい 奇数だけ探索 range() |
132ms |
| action_eratos2() | エラトステネスのふるい 倍数でカウントアップ ×削除時にkeyを探索 |
30sec+ |
| action_eratos3() | エラトステネスのふるい 倍数でカウントアップ array_fill() |
35ms |
<?php class Controller_Primarynumber extends Controller { //$max_num 以下の素数生成 public function action_all($max_num = 100) { $primary = array(); //整数にキャスト $max_num = (int)$max_num; //1以上か？ if($max_num >=1) { //1は素数 $primary[] = 1; for($i=2;$i<=$max_num;$i++) { $is_primary = true; for($j=2;$j<$i;$j++) { if($i % $j === 0) { $is_primary = false; break; } } if($is_primary) { $primary[] = $i; } } } return implode(" ",$primary); } //偶数をのぞく public static function action_odd($max_num = 100) { $primary = array(); //整数にキャスト $max_num = (int)$max_num; //1以上か？ if($max_num >=1) { //1は素数 $primary[] = 1; //2以上か? if($max_num >= 2) { $primary[] = 2; } //偶数は2をのぞいて素数ではないので奇数だけ探索する for($i=3;$i<=$max_num;$i=$i+2) { $is_primary = true; for($j=3;$j<$i;$j=$j+2) { if($i % $j === 0) { $is_primary = false; break; } } if($is_primary) { $primary[] = $i; } } } return implode(" ",$primary); } //エラトステネスのふるい public function action_eratos($max_num=100) { $primary = array(); //整数にキャスト $max_num = (int)$max_num; //1以上か？ if($max_num >=1) { //1は素数 $primary[] = 1; //2以上か? if($max_num >= 2) { $primary[] = 2; //3以上か？ if($max_num >= 3) { //探索リスト 奇数だけ取得 $search = range(3,$max_num,2); //上限の平方根 $sqrt = sqrt($max_num); //探索リストの先頭の値が平方根に達したら終了 //（倍数を探す作業で折り返し地点に達したら終了するイメージ） while(($first = reset($search)) < $sqrt) { //自分を素数に入れる $primary[] = $first; //探索リストの先頭を削除 array_shift($search); //倍数を探索 foreach($search as $k => $v) { //倍数なら探索リストから削除 if($v % $first === 0) { unset($search[$k]); } } } /* A*B = B*Aより、探索リストの残りのうち、平方根以上の値で素数でないものは、 * すべてこれまで探索した値の倍数であるから、削除済み。 * したがって、探索リストの残りはすべて素数。 */ $primary = array_merge($primary,$search); } } } return implode(" ",$primary); } //エラトステネスのふるい //倍数かどうか評価せずに、ループ時に倍数でカウントアップして削除 //13sec public function action_eratos2($max_num=100) { $primary = array(); //整数にキャスト $max_num = (int)$max_num; //1以上か？ if($max_num >=1) { //1は素数 $primary[] = 1; //2以上か? if($max_num >= 2) { $primary[] = 2; //3以上か？ if($max_num >= 3) { //探索リスト 奇数だけ取得 $search = range(3,$max_num,2); //上限の平方根 $sqrt = sqrt($max_num); //探索リストの先頭の値が平方根に達したら終了 //（倍数を探す作業で折り返し地点に達したら終了するイメージ） while(($first = reset($search)) < $sqrt) { //自分を素数に入れる $primary[] = $first; //探索リストの先頭を削除 array_shift($search); //倍数でカウントアップして探索リストから削除 for($i=$first*2;$i<$max_num;$i+=$first) { Arr::delete($search,Arr::search($search,$i)); //上でrange()で偶数を除外してるので、 //これは誤り↓ //unset($search[array_search($i,$search)]); //最初のarray_search(6,$search)でfalseが返り、 //unset($search[false])で$search[0]が削除されてしまう。 //NOTE: //array_search(needle,array)は見つからなかった場合false返す //fuelのArr::search(array,needle)は見つからなかった場合null返す //$array[false] は$array[0]に、array[true]はarray[1]と同じ扱いになる } } /* A*B = B*Aより、探索リストの残りのうち、平方根以上の値で素数でないものは、 * すべてこれまで探索した値の倍数であるから、削除済み。 * したがって、探索リストの残りはすべて素数。 */ $primary = array_merge($primary,$search); } } } return implode(" ",$primary); } //エラトステネスのふるい //倍数でカウントアップ、array_fill() public function action_eratos3($max_num=100) { $primary = array(); //整数にキャスト $max_num = (int)$max_num; //1以上か？ if($max_num >=1) { //1は素数 $primary[] = 1; //2以上か? if($max_num >= 2) { $sqrt = sqrt($max_num); // keyで配列を一気に作る $search = array_fill(2, $max_num - 1, true); // もっと単純に倍数を取り除くだけ for ($i=2; $i<=$sqrt; $i++) { if (isset($search[$i])) { for ($j=$i*2; $j<=$max_num; $j+=$i) { unset($search[$j]); } } } $primary = array_merge($primary,array_keys($search)); } } return implode(" ",$primary); } }
