fork download
copy 
  1. # 
  2. # Euclidean algorithm for finding GCD or GCF
  3. # - from the Wikipedia page
  4. """
  5. The GCD of two numbers is the largest number that divides both of them
  6. without leaving a remainder. The Euclidean algorithm is based on the
  7. principle that the greatest common divisor of two numbers does not change
  8. if the smaller number is subtracted from the larger number.
  9.  
  10. For example, 21 is the GCD of 252 and 105 (252 = 21 * 12; 105 = 21 * 5);
  11. since 252 - 105 = 147, the GCD of 147 and 105 is also 21.
  12.  
  13. Since the larger of the two numbers is reduced, repeating this process
  14. gives successively smaller numbers until one of them is zero.
  15. When that occurs, the GCD is the remaining nonzero number.
  16. By reversing the steps in the Euclidean algorithm, the GCD can be
  17. expressed as a sum of the two original numbers each multiplied by a
  18. positive or negative integer, e.g., 21 = [5 * 105] + [(-2) * 252].
  19. This important property is known as Bezout's identity.
  20. """
  21. from operator import mul
  22.  
  23. def reduce_(tup):
  24.     """
  25.     returns the modulus and minum value of two numbers in a tuple
  26.     tup --> ( max(tup) % min(tup), min(tup) )
  27.     """
  28.     return (max(tup) % min(tup), min(tup))
  29.  
  30. def done(tup):
  31.     """
  32.     returns true if any item in the tuple is 0
  33.     """
  34.     return not reduce(mul, tup)
  35.  
  36. def egcd(tup):
  37.     """
  38.     returns the greatest common divisor of two numbers
  39.  
  40.     Euclidean algorithm
  41.     """
  42.     return (done(reduce_(tup)) and min(tup)) or egcd(reduce_(tup))
  43.  
  44. def egcd3(tup3):
  45.     """
  46.     returns the greatest common divisor of three numbers
  47.  
  48.     Euclidean algorithm
  49.     """
  50.     return egcd((tup3[0], egcd((tup3[1], tup3[2]))))
  51.  
  52. tup3 = (1989, 153, 867)
  53. print tup3, ':\t', egcd3(tup3)
  54.  
  55. tup3 = (1989, 867, 153)
  56. print tup3, ':\t', egcd3(tup3)
  57.  
  58. tup3 = (867, 1989, 153)
  59. print tup3, ':\t', egcd3(tup3)
  60.  
  61. tup3 = (867, 153, 1989)
  62. print tup3, ':\t', egcd3(tup3)
  63.  
  64. tup3 = (153, 1989, 867)
  65. print tup3, ':\t', egcd3(tup3)
  66.  
  67. tup3 = (153, 867, 1989)
  68. print tup3, ':\t', egcd3(tup3)
  69.  
Success #stdin #stdout 0.03s 6716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(1989, 153, 867) :	51
(1989, 867, 153) :	51
(867, 1989, 153) :	51
(867, 153, 1989) :	51
(153, 1989, 867) :	51
(153, 867, 1989) :	51
https://ideone.com/0Ldt2
language:
Python (cpython 2.7.16)
created:
14 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!