EUCLIDEAN ALGORITHM: GCD
gcd(a,b) computes the greatest common divisor of a and b
using the Euclidean algorithm. Delete the print statement
after you have verified that gcd does what it is supposed
to do.
Example:
>>> gcd(12345,54321)
12345 54321 12345
54321 12345 4941
12345 4941 2463
4941 2463 15
2463 15 3
3
Thus the gcd of 12345 and 54321 is 3.
--------------------------------------
def gcd(a,b):
"""gcd(a,b): return greatest common divisor of a and b."""
a, b = abs(a), abs(b)
r = a % b
while r > 0:
print a, b, r
a, b, r = b, r, b % r
return( b )