ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a2 + b2 = c2
例えば, 32 + 42 = 9 + 16 = 25 = 52 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209
まずは素直に書いてみた。
def cof1():
target=1000
(a,b,c) = (1, 1, target - 2)
ans = 0
while a < c:
while b < c:
if a**2 + b**2 == c**2:
ans = a*b*c
break
(b,c) = (b + 1, c - 1)
if ans:
break
else:
(a,b,c) = (a + 1, a + 1, target - a*2 -2)
#print ans
再度見直して、毎回a,b,cの2乗を計算するのは非効率な気がした。
ということで予め1から999それぞれの二乗のlistを作成して、それを参照するようにしてみた。
def cof2():
target=1000
sq = [x**2 for x in range(0,target)] #create
(a,b,c) = (1, 1, target - 2)
ans = 0
while a < c:
while b < c:
if sq[a] + sq[b] == sq[c]:
ans = a*b*c
break
(b,c) = (b + 1, c - 1)
if ans:
break
else:
(a,b,c) = (a + 1, a + 1, target - a*2 -2)
#print ans
結果、1回あたり3.9ミリ秒(下記は100回実行)を削減できた。