Наибольший общий делитель  двух чисел — это наибольшее число, которое делит оба числа без остатка. Например:

 

Наибольший общий делитель используется в:

  • Криптографии (алгоритм RSA)

  • Упрощении дробей

  • Оптимизации алгоритмов

 Основные методы нахождения Наибольшего общего делителя

 Метод перебора (наивный алгоритм)

Принцип:
Перебираем все числа от минимального из двух до 1 и ищем наибольшее, которое делит оба числа.

def gcd_naive(a, b):
    min_num = min(a, b)
    for i in range(min_num, 0, -1):
        if a % i == 0 and b % i == 0:
            return i
    return 1

Сложность:
O(min(a, b)) — неэффективно для больших чисел.

Алгоритм Евклида (классический)

Принцип:
 

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

Пример работы:

#gcd_euclidean(48, 18):
48 % 18 = 12 → НОД(18, 12)
18 % 12 = 6 → НОД(12, 6)
12 % 6 = 0 → НОД(6, 0) → ответ 6

Сложность:
O(log(min(a, b))) — очень эффективно.