Next / Previous / Contents / Shipman's homepage

3.2. The gcd() function

This function implements Euclid's algorithm for finding the greatest common divisor of two numbers a and b.
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.

Defined recursively, this amounts to:
    if  b == 0:
        return a
        return gcd(b, a%b)