## 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.

```##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))

```