все Python 3Алгоритмы и структуры данныхпонятие

НОД / НОК / алгоритм Евклида

математика

НОД (GCD) — наибольший общий делитель. НОК (LCM) = a*b/GCD(a,b). Алгоритм Евклида — O(log min(a,b)).

Синтаксис

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

Свою реализацию писать обычно незачем: math.gcd есть с Python 3.5 (с 3.9 принимает любое количество аргументов), math.lcm — с 3.9. НОК считайте как a // gcd(a, b) * b: деление через / даст float и на больших числах молча потеряет точность. Краевой случай — ноль: math.gcd(0, 0) равен 0, и самодельная формула НОК через деление на нём падает с ZeroDivisionError, тогда как math.lcm просто вернёт 0.

Примеры

# Алгоритм Евклида
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

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности