Как найти НОД двух чисел

НОД — наибольшее число, на которое делятся оба числа без остатка. В Python его находят готовой функцией или алгоритмом Евклида.

Готовая функция

В модуле math есть gcd — она сразу возвращает наибольший общий делитель. На практике используют её.

import math
print(math.gcd(24, 36))   # 12

Алгоритм Евклида

Классический способ понять, как это работает: пока второе число не ноль, заменяем пару (a, b) на (b, остаток a на b). Когда второе станет нулём — первое и есть НОД.

a, b = 24, 36
while b:
    a, b = b, a % b
print(a)   # 12

Почему это красиво

Алгоритм Евклида — один из древнейших и очень элегантный: всего две строки, а работает для любых чисел. Он хорошо показывает силу цикла while и оператора остатка.

Частые вопросы

Что такое a, b = b, a % b? Одновременное присваивание: пара обновляется сразу.

Как найти НОК? Через НОД: НОК = a * b // НОД(a, b).