Finding the Pythagorean triplet that sums to 1000

Project Euler problem 9 says:


A Pythagorean triplet is a set of three natural numbers, a 2 + b2 = c2


For example, 32 + 42 = 9 + 16 = 25 = 52.


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

I am a beginner in programming, especially Python. I got the answer for the problem, but how can I optimize it?

a=0
b=a+1
exit=False

#a loop
for x in xrange(1000):
    a+=1
    b=a+1
    c=b+1
    #b loop
    for y in xrange(1000):
        b+=1            
        if(1000-b-a < 0):
            break
        c = 1000-a-b
        if(a**2 + b**2 == c**2):    
                print "The number is ", a*b*c
                x=1000
                exit = True
        else:
                print "A is ", a ,".\n B is ", b, ".\n  C is ",c,"."
        if exit:
                break
    if exit:
            break

Here are some changes I would do in your code:

-
Since you already have two variables x and y from the loop, you don't need a and b. Get the 3 numbers as - x, y, and 1000 - x - y, and use them.

-
You might well possibly be checking the values same pythagorean triplets twice. Once with x, y, and 1000 - x - y, and then with y, x, 1000 - y - x. For example, when x takes 2 and y takes 3, then you don't want to check this again for x = 3 and y = 2. This might happen, as your inner loop is running from the beginning every time. You can avoid this by iterating from x to 1000.

-
No need of exit boolean variable. Put those loops inside some function, and return as soon as the result is found.

Modified Code:

def specialPythagoreanTriplet(s):

    for a in xrange(s):
        for b in xrange(a, s):
            c = s - a - b;
            if a**2 + b**2 = c**2:
                return (a, b, c)

In addition to all that, you don't really need to iterate till 1000 for values of a and b. The maximum value that a could take should be much less than 1000. Let's find out.

You have:


a + b + c = 1000, and

a < b < c

Replace b and c with a, we get:


a + a + a < 1000

3a < 1000

a < 333

Similarly, you can find out the threshold for b, I'm leaving it for you:

for a in xrange(s / 3):
    for b in xrange(a + 1, s):  # Change `s` to someother value
        # Same as previous code.

StackExchange Code Review Q#37398, answer score: 5