続々 エラトステネスのふるい

エラトステネスのふるいの続き

倍数かどうか評価するまでもなく、倍数でカウンタを回して削除すればよいので、改修したらうんこ以下になった。

	//エラトステネスのふるい
	//倍数かどうか評価せずに、ループ時に倍数でカウントアップして削除
	//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

うんこｗ

中盤のコメントは、fuelのArrクラスとphpのarray_searchを比較しようとしてはまったのでメモ。
$array[false]って$array[0]と一緒なんだな・・・。

勉強になりました。(∩´∀｀;)∩