Project Euler にチャレンジ：Problem 37 PHPでの解答

<?php

// 数字の頭は1,4,6,8,9,0ではない。(2,3,5,7のどれか)
// 数字の最後は1,2,4,5,6,8,9,0 ではない。(3,7 のどちらか)
// 右から消されていくとき、一桁目の数字となるので、途中に0,2,4,5,6,8 は使えない。(1,3,7,9)のどれか。
// 2と5は数字の頭にのみ使える。
// 0,4,6,8 はどこにも使えない数字
// 1桁の数は考慮しないと書かれているので、13からスタート、17,23,27,33,37,53,57,73,77,93,97 とチェックしていき、23が該当する一番小さい素数で、次が37 になる。
// 11個しかないと宣言されているので、11個見つかった時点でループ終了すればよい。
// 2桁の数字で、上記条件で使える素数は 13,17,37,73,97 となる。また、23,37,53,73 の4つが見つかった。

$answer = array();
$head = array(2,3,5,7);
$mid = array(1,3,7,9);
$problem = array(array(3,7));
$count = 0;
$i = 0;

while(true)
{
	// $answer に入れられる数を調べる
	// $problem の数の左に数をくっつけて素数になるか調べる
	foreach($problem[$i] as $v)
	{
		foreach($head as $w)
		{
			$tmp = $w.$v;
			$tmp2 = $tmp;
			$flag = true;
			while(strlen($tmp2) >= 2)
			{
				if(!check_prime($tmp2))
				{
					$flag = false;
					break;
				}
				$tmp2 = substr($tmp2,0,strlen($tmp2) - 1);
			}
			if($flag)
			{
				$answer[] = $tmp;
			}
		}
	}

        // $answer に入れられる数を調べる
        // $problem の数の左に数をくっつけて素数になるか調べる
        foreach($problem[$i] as $v)
        {
                foreach($mid as $w)
                {
                        $tmp = $w.$v;
                        if(check_prime($tmp))
                        {
                                $problem[$i + 1][] = $tmp;
                        }
                }
        }
	if(count($answer) >= 11)
	{
		break;
	}
	$i ++;
}


echo array_sum($answer)."\n";

function check_prime($num)
{
	$flag = true;
        // 素数チェック
        $sqrt = sqrt($num);
        for($i = 3 ;$i <= $sqrt ; $i+=2)
        {
                if($num % $i == 0)
                {
                        $flag = false;
                        break;
                }
        }
	return $flag;
}

?>