It’s in the standard library.
>>> from fractions import gcd
>>> gcd(20,8)
4
Source code from the inspect module in Python 2.7:
>>> print inspect.getsource(gcd)
def gcd(a, b):
“””Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when
b is divided by it, the result comes out positive).
“””
while b:
a, b = b, a%b
return a
As of Python 3.5, gcd is in the math module; the one in fractions is deprecated. Moreover, inspect.getsource no longer returns explanatory source code for either method.
The algorithms with m-n can runs awfully long.
This one performs much better:
def gcd(x, y):
while y != 0:
(x, y) = (y, x % y)
return x