[Project Euler] Problem 9

원문: Problem 9

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

a^(2) + b^(2) = c^(2)

For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

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


피타고라스의 수는 a^(2) + b^(2) = c^(2 를 만족하며 a < b < c를 만족하는 세 자연수의 집합을 말한다.
예를 들어 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2)이다.
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 초가 나왔다.

댓글 없음:

댓글 쓰기