Project Euler No.9

R1001948

次々行くよ。Project Eulerの9問目。

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

ピタゴラスの定理が成立するa2 + b2 = c2のうち、a

こういう、条件に合致する数を求めるのはPrologみたいな論理型言語が向いているような気がします。Mathematicaでも似たようなことができたはず。

でもMatlabで解いていくので、また力業(brute force)で。

N = 1000;
for a = 1:N
  for b = a+1:N
    for c = b+1:N
      if a+b+c == N && a^2+b^2==c^2
        disp(prod([a b c]));
        break;
      end
    end
  end
end

ほんと、総当たりってひどいアルゴリズムO(n3)だもんな〜。(Matlabだと8秒かかったところが、Cで書いたら0.5秒で計算終了・・・)