Extremely inefficient python code

Question

I have made a program to allow users to input the largest possible hypotenuse of a right-angled triangle and my program will list down a list of all possible sides of the triangles. Problem is, the program takes forever to run when I input a value such as 10000. Any suggestions on how to improve the efficiency of the program?

Code:

largest=0
sets=0
hypotenuse=int(input("Please enter the length of the longest side of the triangle"))
for x in range(3,hypotenuse):
    for y in range(4, hypotenuse):
        for z in range(5,hypotenuse):
            if(x<y<z):                   
                 if(x**2+y**2==z**2):
                     commonFactor=False
                     for w in range(2,x//2):
                         if (x%w==0 and y%w==0 and z%w==0):
                             commonFactor=True
                             break
                     if not(commonFactor):
                         print(x,y,z)
                         if(z>largest):
                             largest=z
                         sets+=1
print("Number of sets: %d"%sets)
print("Largest hypotenuse is %d"%largest)

Thanks!

Answer 1

like this?

hypothenuse=10000
thesets=[]
for x in xrange(1, hypothenuse):
    a=math.sqrt(hypothenuse**2-x**2)
    if(int(a)==a):
        thesets.append([x,a])
print "amount of sets: ", len(thesets)
for i in range(len(thesets)):
    print thesets[i][0],thesets[i][1], math.sqrt(thesets[i][0]**2+ thesets[i][1]**2)

edit: changed so you can print the sets too, (this method is in O(n), which is the fastest possible method i guess?) note: if you want the amount of sets, each one is given twice, for example: 15*2=9*2+12*2 = 12*2+9**2

Not sure if i understand your code correctly, but if you give in 12, do you than want all possible triangles with hypothenuse smaller than 12? or do you than want to know the possibilities (one as far as i know) to write 12*2=a*2+b**2?

if you want all possibilities, than i will edit the code a little bit

for all possibilities of a*2+b*2 = c**2, where c< hypothenuse (not sure if that is the thing you want):

hypothenuse=15
thesets={}
for x in xrange(1,hypothenuse):
    for y in xrange(1,hypothenuse):
        a=math.sqrt(x**2+y**2)
        if(a<hypothenuse and int(a)==a):
            if(x<=y):
                thesets[(x,y)]=True
            else:
                thesets[(y,x)]=True
print len(thesets.keys()) 
print thesets.keys()

this solves in O(n**2), and your solution does not even work if hypothenuse=15, your solution gives:

(3, 4, 5) (5, 12, 13) Number of sets: 2

while correct is: 3 [(5, 12), (3, 4), (6, 8)]

since 5*2+12*2=13*2, 3*2+4*2=5*2, and 6*2+8*2=10**2, while your method does not give this third option? edit: changed numpy to math, and my method doesnt give multiples either, i just showed why i get 3 instead of 2, (those 3 different ones are different solutions to the problem, hence all 3 are valid, so your solution to the problem is incomplete?)

Answer 2

Here's a quick attempt using pre-calculated squares and cached square-roots. There are probably many mathematical optimisations.

def find_tri(h_max=10):
  squares = set()
  sq2root = {}
  sq_list = []
  for i in xrange(1,h_max+1):
    sq = i*i
    squares.add(sq)
    sq2root[sq] = i
    sq_list.append(sq)
  #
  tris = []
  for i,v in enumerate(sq_list):
    for x in sq_list[i:]:
      if x+v in squares:
        tris.append((sq2root[v],sq2root[x],sq2root[v+x]))
  return tris

Demo:

>>> find_tri(20)
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]