続々 エラトステネスのふるい
エラトステネスのふるいの続き
倍数かどうか評価するまでもなく、倍数でカウンタを回して削除すればよいので、改修したらうんこ以下になった。
//エラトステネスのふるい //倍数かどうか評価せずに、ループ時に倍数でカウントアップして削除 //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); }
問題
range()で3から初めてさらに偶数を除外してるので、keyとvalueが一致していない。
・keyとvalueが一致していないので、削除するときに要素のkeyを探しに行って計算量が増えてる。
・偶数が削除されてるのに、倍数でループして削除するときには、偶数も含まれてしまってる。
実行時間13sec
うんこw
中盤のコメントは、fuelのArrクラスとphpのarray_searchを比較しようとしてはまったのでメモ。
$array[false]って$array[0]と一緒なんだな・・・。
勉強になりました。(∩´∀`;)∩