Задачи / Числа / НОД двух чисел: алгоритм Евклида

НОД двух чисел: алгоритм Евклида: блок-схема и алгоритм

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

Блок-схема: НОД двух чисел: алгоритм Евклида

Алгоритм по шагам

Ввести a и b.
Пока b ≠ 0: r = a mod b, a = b, b = r.
Вывести a — это НОД.

Открыть блок-схему в редакторе

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

Вход	a = 48, b = 18
Шаг 1	r = 48 mod 18 = 12 → a = 18, b = 12
Шаг 2	r = 18 mod 12 = 6 → a = 12, b = 6
Шаг 3	r = 12 mod 6 = 0 → a = 6, b = 0
Результат	6

Решение на Python

a, b = map(int, input().split())
while b != 0:
    a, b = b, a % b
print(a)

Решение на Pascal

var a, b, r: integer;
begin
  readln(a, b);
  while b <> 0 do
  begin
    r := a mod b;
    a := b;
    b := r;
  end;
  writeln(a);
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: НОД, алгоритм Евклида
начало
ввод a, b
пока b ≠ 0
    r = a mod b
    a = b
    b = r
вывод a
конец

Сложность

O(log min(a, b)) — очень быстро даже для огромных чисел. НОК можно найти как a · b / НОД(a, b).

Частые ошибки

Вариант с вычитанием (a = a − b) тоже верный, но для 1 000 000 и 1 работает миллион шагов.
Порядок присваиваний: сначала нужно сохранить остаток, иначе значение b потеряется.
Выводить b вместо a: после цикла b всегда равен нулю.