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

← Problem 28　　Problem 30 →

確実に重複しないところを除外することでスピードアップさせた。

<?php

// 100^100 等、桁数を考えると、まともに計算してはいけない。
// 素因数分解して、使っている数が一致し、かつ比率も一緒の場合だけ、
// 重複する可能性が存在する。
// よって、重複する可能性があるのは、
// 2,4,8,16,32,64
// 3,9,27,81
// 5,25
// 6,36
// 7,49
// 10,100 
// の場合
// それ以外の場合は重複しないので、回答に全部(99個)足せばよい。

// 素因数を配列に記憶させる

// 10 までの素数
$prime = array(2,3,5,7);

// 素因数を記憶する配列
$num = array();

// 数列を記憶する配列
$distinct = array();

$answer = 0;
for($a = 2 ; $a <= 100 ; $a++)
{
	if($a == 2 or $a == 4 or $a == 8 or $a == 16 or $a == 32 or $a == 64 or $a == 3 or $a == 9 or $a == 27 or $a == 81 or $a == 5 or $a == 25 or $a == 6 or $a == 36 or $a == 7 or $a == 49 or $a == 10 or $a == 100)
	{
		$num[$a] = array();
		$tmp = $a;
		foreach($prime as $v)
		{
			while($tmp % $v == 0)
			{
				@$num[$a][$v]++;
				$tmp = $tmp / $v;
			}
		}
		if($tmp != 1)
		{
			@$num[$a][$tmp] ++; 
		}
	
		for($b = 2 ; $b <= 100 ; $b++)
		{
			// 素因数分解したものの積を作成する
			$tmp_array = array();
			foreach($num[$a] as $k => $v)
			{
				$tmp_array[$k] = $v * $b;
			}
	
			// 今までの配列の中に、同じものがないかを比較する
			$flag = true;
			foreach($distinct as $v)
			{
				if($tmp_array === $v)
				{
					$flag = false ;
					break;
				}
			}
			// 今までの配列の中に同じものがなかった場合、配列にデータを挿入する
			if($flag)
			{
				$distinct[] = $tmp_array;
			}
		}
	}
	else
	{
		$answer += 99;
	}
}
	
$answer += count($distinct);

echo $answer;

?>