A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that a and b are two positive integers: ・If b = 0, then the answer is a ・Otherwise, gcd(a, b) is the same as gcd(b, a % b) See this website for an example of Euclid's algorithm being used to find the gcd. http://en.wikipedia.org/wiki/Euclidean_alg…

gcdIter.py

def gcdIter(a, b):
  '''
  a, b: positive integers
  
  returns: a positive integer, the greatest common divisor of a & b.
  '''
  testValue = min(a, b)

  # Keep looping until testValue divides both a & b evenly
  while a % testValue != 0 or b % testValue != 0:
    testValue -= 1

  return testValue

gcdRecur.py

def gcdRecur(a, b):
  '''
  a, b: positive integers

  returns: a positive integer, the greatest common divisor of a & b.

  See this website for an example of Euclid's algorithm being used to find the gcd.
  http://en.wikipedia.org/wiki/Euclidean_algorithm#Concrete_example
  '''
  if b == 0:
    return a
  else:
    return gcdRecur(b, a%b)