Euclid’s algorithm
Euclid’s algorithm provides a fast way to calculate the greatest common devisor of two integers. See also Extended Euclid’s algorithm
Implementation
Haskell
gcd' :: (Integral a) => a -> a -> a
gcd' a 0 = a
gcd' a b = gcd b (mod a b)Python
def gcd(a, b):
return a if not b else gcd(b, a % b)Practice problems
- 2017. Contemporary abstract algebra, p. 23 (§0 exercises 2, 19, 20)