Example 6: Finding the greatest common divisor of two integers (GCD)

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.

# Euclid's algorithm for computing the gcd
# Nonrecursive version is discussed in for versus while loop post
# see 02Loops example_12 GCDWhileLoop.py

def findGCD(n, m):
    while n != 0:
        gcd = n
        n = m % n
        m = gcd

    return gcd

def findGCDRecur(n, m):
    if n != 0:
        return findGCDRecur(m % n, n)
        return m

a = input('Please input the first integer:')
b = input('Please input the second integer:')


For more information on Euclid’s algorithm see