Pythagorean triplet adding up to 1000

Question

Project Euler problem 9 says:

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\$.

My code finds the correct solution to the problem. The problem is it takes 47.6 seconds to get it, so I'd like to optimize it, but don't know exactly how to do so further. I've already reduced the range of the for loops.

import time
s=time.time()
a=0
b=0
c=0
for i in range(1,499): #max value for any side of the triangle must be less than the semiperimeter
 for j in range(i,499):
 for k in range(j,499):
 if(i+j+k==1000 and i**2+j**2==k**2):
 a=i
 b=j
 c=k
 break #the solution is unique, so when it finds a solution, it doesnt need to go through any other loops.
print(a*b*c,time.time()-s)

Answer 1

for i in range(1,499): #max value for any side of the triangle must be less than the semiperimeter
 for j in range(i,499):
 for k in range(j,499):
 if(i+j+k==1000 and i**2+j**2==k**2):

There are a couple quick optimizations.

for i in range(1,333):

You can restrict this beyond 499. We know that \$ a < b < c\$ and \$a + b + c = 1000\,ドル so we can say that \3ドル*a < 1000\$ or \$a \leq 333\$.

 for j in range(i,499): #max value for any side of the triangle must be less than the semiperimeter
 k = 1000 - i - j

We don't need to iterate to find k. We can calculate it from i and j since we know that the three sum to 1000.

 if (i**2+j**2==k**2):

So we can just check that it's a Pythagorean triple. The sum will always be correct, as that's how we select k.

Just calculating k instead of iterating to find it should reduce the time to less than a second.

Answer 2

Another easy optimisation would be to fix the early return. As you said, you should stop the search when you found the result, but by using break, you only break the innermost loop, and the search continues. I suggest moving the search into a function which would return when the result is found. This by itself reduces the run time by almost 50%:

import time
def pythagorean_triplet(limit):
 # value of any side of the triangle must be less than the semiperimeter
 semiperimeter = limit // 2
 for i in range(1, semiperimeter):
 for j in range(i, semiperimeter):
 for k in range(j, semiperimeter):
 if(i+j+k == limit and i**2+j**2 == k**2):
 # the solution is unique, so when it finds a solution, it
 # doesnt need to go through any other loops.
 return i, j, k
s = time.time()
a, b, c = pythagorean_triplet(1000)
print(a*b*c, time.time()-s)

The above snippet also includes some style changes to conform to pep8, and changes the second range argument (semiperimeter) from 499 to 500, since the range function goes up to but not including the stop value.