all Python 3Algorithms & data structuresterm

GCD / LCM / Euclidean algorithm

math

GCD is the greatest common divisor. LCM = a*b/GCD(a, b). Euclid's algorithm takes O(log min(a, b)).

Syntax

def gcd(a, b):
    while b: a, b = b, a%b
    return a

You rarely need your own version: math.gcd has been there since Python 3.5 (variadic since 3.9), and math.lcm was added in 3.9. Compute the LCM as a // gcd(a, b) * b — using / turns it into a float and silently loses precision on big integers. Watch the zero case: math.gcd(0, 0) is 0, so a hand-rolled LCM that divides by it raises ZeroDivisionError, while math.lcm simply returns 0.

Examples

# Алгоритм Евклида
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
print(gcd(48, 18))  # → 6
print(gcd(100, 75)) # → 25
# Рекурсивный
def gcd_rec(a, b):
    if b == 0: return a
    return gcd_rec(b, a % b)
print(gcd_rec(56, 98))  # → 14
# НОК
def lcm(a, b):
    return a * b // gcd(a, b)
print(lcm(4, 6))   # → 12
print(lcm(12, 18)) # → 36

# Python 3.9+
# Стандартная библиотека
import math
print(math.gcd(48, 36))    # → 12
print(math.lcm(4, 6))      # → 12
print(math.gcd(0, 5))      # → 5
print(math.gcd(12, 18, 24))  # → 6 (Python 3.9+)

# Расширенный алгоритм Евклида
def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a%b)
    return g, y, x - (a//b)*y
print(extended_gcd(48, 18))  # → (6, -1, 3), то есть 48*(-1)+18*3=6

# Python 3.9+
# Несколько чисел
from functools import reduce
import math
nums = [12, 18, 24, 36]
print(reduce(math.gcd, nums))  # → 6
print(reduce(math.lcm, nums))  # → 72

GCD / LCM / Euclidean algorithm

Syntax

Examples

See also