[Project Euler] Problem 9

원문: Problem 9

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.

피타고라스의 수는 a² + b² = c² 를 만족하며 a b c를 만족하는 세 자연수의 집합을 말한다.
예를 들어 3² + 4² = 9 + 16 = 25 = 5²이다.
a + b + c = 1000 를 만족하는 피타고라스의 수는 정확히 한 개가 존재한다.
그들의 곱인 abc 를 찾아라.

Python

[(1000-c-b)*b*c for c in range(0, 1000) for b in range(0, 1000) if (1000-c-b)**2+b**2 == c**2]

접기

이 코드로는 1.9002 초가 나왔다. 여기에 수학을 적용해서 범위를 줄이면 아래 코드가 된다.

Python 2

c^2 >= 2ab, a+b+c = 1000, a^2+b^2=c^2 를 모두 사용해서 c 의 범위를 줄이면 1000 >= c >= root(2) * 1000 - 1000 이 나온다. 여기다가 a < b 를 사용하면 (1000-c)/2 < b <= 585 가 된다.

[(1000-c-b)*b*c for c in range(415, 1000) for b in range((1000-c)//2, 586) if (1000-c-b)**2+b**2 == c**2]

접기

이 코드로는 0.49670 초가 나왔다.