Python Implementation
Now that you understand the algorithm, let's test various values to determine their GCD. The main feature of the implementation is that the algorithm requires one single while loop. This observation means that the Euclidean algorithm can efficiently find the GCD. Therefore, this algorithm is an excellent candidate for application in cryptographic applications.
Write a Python program to implement the Euclidean Algorithm to compute the greatest common divisor (GCD).
Note: In mathematics, the Euclidean algorithm[a], or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 = 252 − 105.
Sample Solution:
from math import *
def euclid_algo(x, y, verbose=True):
if x < y: # We want x >= y
return euclid_algo(y, x, verbose)
print()
while y != 0:
if verbose: print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y))
(x, y) = (y, x % y)
if verbose: print('gcd is %s' % x)
return x
euclid_algo(150, 304)
euclid_algo(1000, 10)
euclid_algo(150, 9)
Sample Output:
304 = 2 * 150 + 4
150 = 37 * 4 + 2
4 = 2 * 2 + 0
gcd is 2
1000 = 100 * 10 + 0
gcd is 10
150 = 16 * 9 + 6
9 = 1 * 6 + 3
6 = 2 * 3 + 0
gcd is 3
Pictorial Presentation:
Flowchart:
Source: w3resource, https://www.w3resource.com/python-exercises/math/python-math-exercise-76.php
This work is licensed under a Creative Commons Attribution 4.0 License.