Problem 9 - Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

링크

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

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

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

python

for a in range(1, 999): for b in range(a, 999): c = 1000 - (a+b) if (a*a + b*b == c*c): print a*b*c

python - more efficient

A Pythagorean triplet (a,b,c) has gcd(a,b) = gcd(b,c) = gcd(c,d), and is by definition primitive if gcd(a,b,c) = 1

and Pythagorean triplets can be represented as

a = m^2 - n^2, b = 2mn, c = m^2 + n^2

while 

m > n > 0

then Pythagorean triplet will be primitive iff exactly one of m, n is even and gcd(m, n)=1

Efficient algorithm use it

import math import fractions s = 1000 s2 = s / 2 mlimit = int(math.ceil(math.sqrt(s2)) - 1) for m in range(2, mlimit + 1): if s2 % m == 0: sm = s2 / m while sm % 2 == 0: sm = sm / 2 if m % 2 == 1: k = m + 2 else: k = m + 1 while k < 2*m and k <= sm: if sm % k == 0 and fractions.gcd(k, m) == 1: d = s2 / (k * m) n = k - m a = d * (m * m - n * n) b = 2 * d * m * n c = d * (m * m + n * n) print a, b, c k = k + 2