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

← Problem 40　　Problem 42 →

再帰を利用することで、パンデジタル数の抽出を速くした。

<?php
// 素数を見つけてからパンデジタル数か否かをチェックすると、すごく時間がかかるので、
// パンデジタル数か否かチェックしたうえで、素数か否かを判定する

$answer = 0;

$array = array(9,8,7,6,5,4,3,2,1);
while(count($array) > 0)
{
	// 配列を並び替えて、ひとつの数値にする
	foreach($array as $v)
	{
		create_p($array,$v,$v);
	}
	array_shift($array);
}

function create_p($array,$num1,$num2)
{
	$result = array_diff($array,array($num1));
	if(count($result) > 0)
	{
		foreach($result as $v)
		{
			create_p($result,$v,$num2.$v);
		}
	}
	else
	{
		check_prime($num2);
	}
}

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

?>