НОД двух чисел

Наибольший общий делитель (НОД)

Наибольший общий делитель (НОД) двух чисел — это наибольшее положительное целое число, на которое оба исходных числа делятся без остатка. Алгоритм Евклида — это древний и эффективный метод его вычисления, основанный на простой математической идее: НОД(a, b) = НОД(b, a mod b).

Алгоритм Евклида: основная идея

Алгоритм работает на принципе, что если a > b, то:

• НОД(a, b) = НОД(b, a mod b)
• Процесс повторяется, пока остаток не станет равным нулю
• Когда остаток равен нулю, последний делитель и есть НОД

Пример:

НОД(48, 18):
48 = 18 * 2 + 12  → НОД(18, 12)
18 = 12 * 1 + 6   → НОД(12, 6)
12 = 6 * 2 + 0    → Остаток 0, значит НОД = 6

Итеративная реализация

def gcd(a: int, b: int) -> int:
    """
    Находит наибольший общий делитель двух чисел алгоритмом Евклида.
    
    Args:
        a: Первое целое число
        b: Второе целое число
    
    Returns:
        НОД чисел a и b
    
    Raises:
        ValueError: Если одно из чисел равно нулю
    """
    if a == 0 or b == 0:
        raise ValueError("Both numbers must be non-zero")
    
    # Работаем с абсолютными значениями
    a, b = abs(a), abs(b)
    
    # Алгоритм Евклида
    while b != 0:
        a, b = b, a % b
    
    return a

# Тесты
print(gcd(48, 18))    # 6
print(gcd(100, 25))   # 25
print(gcd(17, 13))    # 1
print(gcd(1071, 462)) # 21
print(gcd(-48, 18))   # 6 (работает с отрицательными)

Рекурсивная реализация

def gcd_recursive(a: int, b: int) -> int:
    """
    Рекурсивная версия алгоритма Евклида.
    """
    if a == 0 or b == 0:
        raise ValueError("Both numbers must be non-zero")
    
    a, b = abs(a), abs(b)
    
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

# Тесты
print(gcd_recursive(48, 18))    # 6
print(gcd_recursive(100, 25))   # 25
print(gcd_recursive(17, 13))    # 1

Анализ сложности

Временная сложность: O(log(min(a, b)))

• Это связано с тем, что на каждой итерации большее число примерно уменьшается в 2 раза
• Поэтому максимум log(n) итераций

Пространственная сложность:

• Итеративная версия: O(1) — использует только несколько переменных
• Рекурсивная версия: O(log(min(a, b))) — глубина стека вызовов

Расширенный алгоритм Евклида

Расширенный алгоритм также находит коэффициенты Безу (x и y), такие что: a * x + b * y = НОД(a, b)

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """
    Расширенный алгоритм Евклида.
    Возвращает (gcd, x, y) такие что: a*x + b*y = gcd
    """
    if b == 0:
        return a, 1, 0
    
    gcd_val, x1, y1 = extended_gcd(b, a % b)
    
    x = y1
    y = x1 - (a // b) * y1
    
    return gcd_val, x, y

# Пример
gcd_val, x, y = extended_gcd(48, 18)
print(f"НОД(48, 18) = {gcd_val}")
print(f"48 * {x} + 18 * {y} = {gcd_val}")
print(f"Проверка: 48 * {x} + 18 * {y} = {48*x + 18*y}")
# Результат: 48 * (-1) + 18 * 3 = 6

Практические применения

Сокращение дроби

def reduce_fraction(numerator: int, denominator: int) -> tuple[int, int]:
    """Сокращает дробь числитель/знаменатель"""
    g = gcd(numerator, denominator)
    return numerator // g, denominator // g

print(reduce_fraction(48, 18))  # (8, 3)
print(reduce_fraction(100, 25)) # (4, 1)

Нахождение НОК (Наименьшего общего кратного)

def lcm(a: int, b: int) -> int:
    """Находит наименьшее общее кратное"""
    return abs(a * b) // gcd(a, b)

print(lcm(12, 18))  # 36
print(lcm(21, 14))  # 42

Проверка взаимной простоты

def are_coprime(a: int, b: int) -> bool:
    """Проверяет, являются ли два числа взаимно простыми (НОД = 1)"""
    return gcd(a, b) == 1

print(are_coprime(17, 13))  # True
print(are_coprime(12, 8))   # False

Сравнение методов

Оптимизация: побитовый алгоритм Евклида

def gcd_binary(a: int, b: int) -> int:
    """
    Бинарный алгоритм Евклида (использует побитовые операции).
    Быстрее обычного Евклида на некоторых процессорах.
    """
    if a == 0:
        return b
    if b == 0:
        return a
    
    # Оба чётные
    if ((a & 1) == 0) and ((b & 1) == 0):
        return gcd_binary(a >> 1, b >> 1) << 1
    # a чётный, b нечётный
    elif (a & 1) == 0:
        return gcd_binary(a >> 1, b)
    # a нечётный, b чётный
    elif (b & 1) == 0:
        return gcd_binary(a, b >> 1)
    # Оба нечётные
    else:
        return gcd_binary((a - b) >> 1, b) if a > b else gcd_binary((b - a) >> 1, a)

print(gcd_binary(48, 18))    # 6
print(gcd_binary(100, 25))   # 25

Заключение

Алгоритм Евклида — это элегантное и эффективное решение для нахождения НОД. С временной сложностью O(log n) он работает быстро даже для очень больших чисел. Понимание этого алгоритма критично для решения множества задач в теории чисел, криптографии и компьютерных алгоритмах.