fork download
copy 
  1. import time
  2.  
  3. def pythagorean_triple(s):
  4.     """ Yield all Pythagorean triples that sum to positive integer s
  5.     https://e...content-available-to-author-only...a.org/wiki/Pythagorean_triple says that 
  6.     all triples can be generated by
  7.         a=k*(m*m-n*n)
  8.         b=k*2*m*n
  9.         c=k*(m*m+n*n)
  10.     so from a+b+c=s follows
  11.     k*2* m*(m+n)=s
  12.     """
  13.     if s % 2:
  14.         return          # No triples sum to an odd number
  15.     factors=[]
  16.     for d in range(1,int(s**.5)+1):
  17.         if s%d==0:
  18.             factors.append(d)
  19.             if s>d*d:
  20.                 factors.append(s//d)
  21.     factors.sort()
  22.  
  23.     for k in factors:
  24.         q=s//k   # = 2* m*(m+n)
  25.         if q%2==0:
  26.             p=q/2  # = m*(m+n) 
  27.             for m in factors: # m is a factor of p and so a factor of s
  28.                 if p%m==0:
  29.                     n=p//m-m
  30.                     if 0<n and n<m:
  31.                         a=k*(m*m-n*n)
  32.                         b=k*2*m*n
  33.                         c=k*(m*m+n*n)
  34.                         yield(a,b,c)
  35.  
  36.  
  37. def test(s):
  38.     start = time.time()
  39.     print [[a , b , c] for a, b, c in pythagorean_triple(s)]
  40.     print 'Time taken', time.time() - start
  41.  
  42. test(1000)   
  43. test(1356780)
  44. test(7064950394940)
  45.  
  46.  
Success #stdin #stdout 1.43s 9104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[375, 200, 425], [375, 200, 425]]
Time taken 0.000114917755127
[[542712, 226130, 587938], [226130, 542712, 587938], [339195, 452260, 565325]]
Time taken 0.000249862670898
[[2825980157976L, 1177491732490L, 3061478504474L], [1177491732490L, 2825980157976L, 3061478504474L], [1766237598735L, 2354983464980L, 2943729331225L]]
Time taken 1.31435990334
https://ideone.com/HIxLgN
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!