A Pythagorean triple (a natural number that satisfies the Pythagorean theorem) is a set of numbers that satisfy the following equation with a <b <c.
a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52.
There is only one Pythagoras triplet with a + b + c = 1000. Calculate the product abc of these. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209
First of all, I wrote it obediently.
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
I felt that it would be inefficient to review it again and calculate the squares of a, b, and c each time.
So I created a list of squares from 1 to 999 in advance and tried to refer to it.
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
As a result, we were able to reduce 3.9 milliseconds per time (the following is executed 100 times).
Recommended Posts