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.

rational.py
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:

rational.py
    if  b == 0:
        return a
    else:
        return gcd(b, a%b)