Euclid's Algorithm in Python?

Antoon Pardon apardon at
Fri Aug 5 09:50:09 CEST 2005

Op 2005-08-05, Jordan Rastrick schreef <jrastrick at>:
> Raising an assertion error for a < b is a bit of overkill, since its
> not really a case of bad input. So normally you see Euclid done like
> this:
> def gcd(a,b): # All lowercase for a function is a bit more
> conventional.
>     if a < b:
>          a, b = b, a # Ensures a >= b by swapping a and b if nessecary
>     while b != 0: # Note parentheses are unnessecary here in python
>          a, b = b, a % b
>     return a
> A bit more concise and no less readable (IMO).

The if test is unnecessary. Should a be smaller than b, the two values
will be swapped by the while body.

Antoon Pardon

More information about the Python-list mailing list