fork download
copy 
  1. import time
  2.  
  3. def find_pythagorean(s):
  4.     """ Yield all Pythagorean triples that sum to positive integer s 
  5.     this function is from 
  6.     http://c...content-available-to-author-only...e.com/questions/60652/project-euler-9-pythagorean-triplets/60671#comment-110333
  7.     """
  8.     count=0
  9.     if s % 2:
  10.         return          # No triples sum to an odd number
  11.     hs2 = s * s / 2
  12.     for a in xrange(1, int(s * (1 - .5**.5)) + 1):
  13.         if (hs2 - s * a) % (s - a) == 0:
  14.             b = (hs2 - s * a) / (s - a)
  15.             c=s-a-b
  16.             if a+b+c>37:
  17.                 count=1
  18.             else:
  19.                 count=0
  20.     return(count)
  21.  
  22.  
  23. def pythagorean_triple(s):
  24.     """ Yield all Pythagorean triples that sum to positive integer s
  25.     https://e...content-available-to-author-only...a.org/wiki/Pythagorean_triple says that 
  26.     all triples can be generated by
  27.         a=k*(m*m-n*n)
  28.         b=k*2*m*n
  29.         c=k*(m*m+n*n)
  30.     so from a+b+c=s follows
  31.     k*2* m*(m+n)=s
  32.     """
  33.     count=0
  34.     if s % 2:
  35.         return          # No triples sum to an odd number
  36.     factors=[]
  37.     for d in range(1,int(s**.5)+1):
  38.         if s%d==0:
  39.             factors.append(d)
  40.             if s>d*d:
  41.                 factors.append(s//d)
  42.     factors.sort()
  43.  
  44.     for k in factors:
  45.         q=s//k   # = 2* m*(m+n)
  46.         if q%2==0:
  47.             p=q/2  # = m*(m+n) 
  48.             for m in factors: # m is a factor of p and so a factor of s
  49.                 if p%m==0:
  50.                     n=p//m-m
  51.                     if 0<n and n<m:
  52.                         a=k*(m*m-n*n)
  53.                         b=k*2*m*n
  54.                         c=k*(m*m+n*n)
  55.                         if a+b+c>37:
  56.                             count=1
  57.                         else:
  58.                             count=0
  59.     return(count)
  60.  
  61.  
  62. def test(s,ntimes):
  63. 	cnt=0
  64. 	start = time.time()
  65. 	for i in range(ntimes):
  66. 	    cnt=find_pythagorean(s)
  67. 	diff_time1=time.time() - start 
  68.  
  69. 	start = time.time()
  70. 	for i in range(ntimes):
  71. 	    cnt=pythagorean_triple(s)
  72. 	diff_time2=time.time() - start 
  73. 	print((s, diff_time1, diff_time2, diff_time1/diff_time2, ntimes))
  74.  
  75. 	if cnt==1234567:
  76. 		print(cnt)
  77.  
  78. print(("a+b+c", "sec(simple alg)", "sec(euler alg)", "simple/euler", "executions"))
  79. test(770,1000)
  80. test(1000,1000)
  81. test(1006,1000)
  82.  
  83. test(10010,1000)
  84. test(10000,1000)
  85. test(10006,1000)
  86.  
  87. test(102102,10)
  88. test(100000,10)
  89. test(100042,10)
  90.  
  91. test(1000000,1)
  92. test(1000018,1)
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
Success #stdin #stdout 3.46s 7900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
('a+b+c', 'sec(simple alg)', 'sec(euler alg)', 'simple/euler', 'executions')
(770, 0.04948687553405762, 0.03587198257446289, 1.3795411344029562, 1000)
(1000, 0.06376004219055176, 0.049881935119628906, 1.278219099512475, 1000)
(1006, 0.0630950927734375, 0.009338855743408203, 6.756190962471279, 1000)
(10010, 0.6293511390686035, 0.10950207710266113, 5.747389964836648, 1000)
(10000, 0.6231749057769775, 0.11575698852539062, 5.3834754490031305, 1000)
(10006, 0.62192702293396, 0.01711297035217285, 36.34243559914736, 1000)
(102102, 0.20213890075683594, 0.0037381649017333984, 54.07436698769054, 10)
(100000, 0.20229697227478027, 0.0025560855865478516, 79.14327021733047, 10)
(100042, 0.20339393615722656, 0.00048613548278808594, 418.38940657184895, 10)
(1000000, 0.22823405265808105, 0.0005497932434082031, 415.1270598438855, 1)
(1000018, 0.22992205619812012, 0.00013709068298339844, 1677.1530434782608, 1)
https://ideone.com/diqauf
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!