続：四角い車輪の再発明 ～エラトステネスのふるい

この前のエントリアホなりに素数を生成するプログラムをつくってみる - おはヨーグルト。
でなんも考えずに素数を生成するプログラムを書きました。σ(^_^;)アセアセ...
3以上の場合偶数を削除するだけで、何のひねりもない。

素数　探索でぐぐって、エラトステネスのふるいを発見。

エラトステネスの篩 - Wikipedia
を見て自分なりに書いてみました。ｃ⌒っﾟдﾟ)っφ　カキカキ...

序盤で2の倍数を探索する計算量が強烈なので、3以上の場合は、奇数だけ探索リストにいれる。

	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);


	}

さて、突っ込みどころはあるが、うまく動いたので実行時間を計る。

1万までの素数を出力

こないだつくったやつ
function action_all 選手（全部探索）：600ms
function action_odd 選手（3以上の場合奇数だけ探索）：310ms

function action_eratos（3以上の場合奇数だけ探索+エラトステネスのふるい）:
13ms

ｷﾀ - .∵･(ﾟ∀ﾟ)･∵. - ｯ!!