Given two integers, the GCD is the largest positive integer that divides the two numbers without a remainder. For example, the GCD of 32 and 24 is 8. The loop material presented two non-recursive programs: a while-loop solution based on Euclid’s algorithm and a solution using a for-loop.
Euclid’s algorithm is based on a property that can be expressed recursively:
- GCD(n, m) = m when n = 0
- GCD(n, m) = GCD(m mod n, n) when n > 0
Here is the Python program.
##GCD.py # Euclid's algorithm for computing the gcd # Nonrecursive version is discussed in for versus while loop post # see 02Loops example_12 GCDWhileLoop.py ##non-recursive def findGCD(n, m): while n != 0: gcd = n n = m % n m = gcd return gcd ##recursive def findGCDRecur(n, m): if n != 0: return findGCDRecur(m % n, n) else: return m a = input('Please input the first integer:') b = input('Please input the second integer:') print(findGCD(a,b)) print(findGCDRecur(a,b))
For more information on Euclid’s algorithm see