204 http://inventwithpython.com/hacking
Email questions to the author: [email protected]
Figure 14 - 7. Euclid may or may not have looked like this.Of course since no likeness or description of Euclid exists in any historical document, no one
knows what he actually looked like at all. (Artists and sculptors just make it up.) This statue could
also be called, “Statue of Some Guy with a Beard”.
Euclid’s GCD algorithm is short. Here’s a function that implements his algorithm as Python code,
which returns the GCD of integers a and b:
def gcd(a, b):
while a != 0:
a, b = b % a, a
return b
If you call this function from the interactive shell and pass it 24 and 30 for the a and b
parameters, the function will return 6. You could have done this yourself with pencil and paper.
But since you’ve programmed a computer to do this, it can easily handle very large numbers:
gcd(24, 30)
6
gcd(409119243, 87780243)
6837
How Euclid’s algorithm works is beyond the scope of this book, but you can rely on this function
to return the GCD of the two integers you pass it.