Алгоритм Евклида на Python по шагам: НОД двух чисел

НОД: алгоритм Евклида: разбор по шагам

Алгоритм Евклида основан на том, что НОД(a, b) = НОД(b, a % b). Числа быстро уменьшаются, и когда остаток становится нулём, ответ — оставшееся a.

Наименьшее общее кратное считают через НОД: НОК = a · b / НОД.

На что смотреть в пошаговом режиме

• как меняется пара a, b на каждой итерации;
• сколько итераций понадобилось;
• расчёт НОК через НОД.

Код примера

a = int(input())
b = int(input())
x, y = a, b
while b != 0:
    a, b = b, a % b
gcd = a
print('НОД =', gcd)
print('НОК =', x * y // gcd)

Код уже в редакторе. Нажмите «По шагам» и листайте шаги кнопкой ▶ или клавишей →. Код можно менять и запускать заново.

Отладчик Python: как пользоваться и частые вопросы