Greatest Common Divisor

  1. The greatest common divisor (GCD) of two values can be computed using Euclid's algorithm.
  2. Starting with the values m and n, we repeatedly apply the formula: n, m = m, n%m until m is 0.
  3. At that point, n is the GCD of the original m and n.
  4. Write a function gcd() that finds the GCD of two numbers using this algorithm.
Test your function with the following main program: 

def main():
    a, b = eval(input("Please input two positive integers -- "))
    while (a>0 and b>0):
        print("GCD({0},{1}) = {2}".format( a, b, gcd(a,b) ) )
        a, b = eval(input("Please input two positive integers -- "))

if __name__ == "__main__":
    main()
The program may run as follows. 

Please input two positive integers -- 33, 90
GCD(33,90) = 3
Please input two positive integers -- 58, 42
GCD(58,42) = 2
Please input two positive integers -- 48, 42
GCD(48,42) = 6
Please input two positive integers -- 48, 36
GCD(48,36) = 12
Please input two positive integers -- 72, 81
GCD(72,81) = 9
Please input two positive integers -- 0, 0