This function implements Euclid's algorithm for finding
the greatest common divisor of two numbers
def gcd ( a, b ): '''Greatest common divisor function; Euclid's algorithm. [ a and b are integers -> return the greatest common divisor of a and b ] '''
Euclid's algorithm is easily defined as a recursive function. See Structure and Interpretation of Computer Programs by Abelson and Sussman, ISBN 0-262-01153-0, pp. 48-49.
The GCD of any number
and zero is zero.
The GCD of any two nonzero numbers
is the same
Defined recursively, this amounts to:
if b == 0: return a else: return gcd(b, a%b)