← Все вопросы
Как найти НОД двух чисел? Алгоритм Евклида
12
Нужно найти наибольший общий делитель двух чисел. Перебирать все делители долго. Слышал про алгоритм Евклида — как он работает и почему такой быстрый?
3 ответа
23
✓ Принятый ответ — помог автору
Алгоритм Евклида: НОД(a, b) = НОД(b, a % b), и так пока второе число не станет нулём. Тогда первое — это и есть ответ.
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(48, 36)) # 12
Почему быстро: остаток уменьшает числа очень резко, шагов получается O(log(min(a, b))). Даже для огромных чисел — считанные итерации.
В Python вообще есть готовое: math.gcd(48, 36).
Oleg Lugovskoi автор: math.gcd то что искал, спасибо 🙏 · 17 месяцев назад
8
math.gcd(a, b).
6
Рекурсивно в одну строку:
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
А НОК через НОД: a * b // gcd(a, b).
Ваш ответ
Войдите, чтобы ответить на вопрос.
