アホなりに素数を生成するプログラムをつくってみる

上記、四角い車輪の再発明になるのは承知のうえで。

半年前に転職活動したときに、100までの素数を生成するプログラムを書いてください。といわれて紙と鉛筆を渡された。制限時間は30分。

もちろん誰でもできるのは想定内で、アルゴリズムのスマートさを見ようという魂胆だったようだけど、ど素人のおいらっちは大爆死。

アルゴリズム理論どころか、書けないという醜態をさらしましたｗ

あれから半年。ふと思い立って、fuelphpで書いてみました。

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

}

全部探索するaction_allと
3以上の場合、奇数だけ探索するaction_oddの二つをつくった。

10000までの素数をはき出させて、profilerで実行時間計測。
action_all選手は 600ms
action_odd選手は 310ms
うーん、だいぶ違うね。