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

<?php

// 素因数分解して4つの要素がある数の最小数は 2*3*5*7 = 210 になる。
// 4つの連続した数を探すので、4つおきに探して、要素が4つになったときに前後を調べると、調べる対象が約1/4 になる。
// 奇数のほうが4つの要素がある数として、大きな数になるはずなので、4つおきの数は奇数を調べたほうが調べる対象が減るはず
// 3*5*7*11 が奇数で4つの数がある最小数
$answer = 1155;
$answer2 = 0;
$num = 0;

while(true)
{
	if(count_primes_factor($answer) == 4)
	{
		$answer2 = $answer;
		$num++;
		// 前後3つの数を調べる
		for($tmp = $answer - 1 ; $tmp >= $answer - 3 ; $tmp--)
		{
			if(count_primes_factor($tmp) == 4)
			{
				$answer2 = $tmp;
				$num++;
			}
			else
			{
				break;
			}
		}
		for($tmp = $answer + 1; $tmp <= $answer + 3 ; $tmp++)
		{
			if(count_primes_factor($tmp) == 4)
			{
				$num++;
			}
			else
			{
				break;
			}
		}
	}
	if($num == 4)
	{
		break;
	}
	else
	{
		$num = 0;
	}
	$answer+=4;
}
echo $answer2."\n";

// 素因数の要素数をカウントする関数
function count_primes_factor($num)
{
	$count = 0;
	$i = 3;
	while($num >= $i)
	{
		$flag = true;
		while($num % $i == 0)
		{
			// 初回だけカウントする
			if($flag)
			{
				$flag = false;
				$count++;
			}
			$num = $num / $i;
		}
		$i +=2;
	}
	if($num % 2 == 0)
	{
		$count++;
	}
	return $count;
}


?>