Наибольший общий делитель (НОД)

Алгоритм Евклида для нахождения наибольшего общего делителя двух чисел.

НОД — это самое большое число, на которое оба числа делятся без остатка. Например, НОД(48, 18) = 6.

Идея алгоритма

Алгоритм Евклида основан на простом свойстве: $\text{НОД}(a, b) = \text{НОД}(b, a \bmod b)$.

То есть НОД двух чисел не меняется, если большее число заменить остатком от деления на меньшее. Повторяем, пока одно из чисел не станет 0 — тогда второе число и есть ответ.

Пример по шагам:

НОД(48, 18): остаток от 48 / 18 = 12 → НОД(18, 12)
НОД(18, 12): остаток от 18 / 12 = 6 → НОД(12, 6)
НОД(12, 6): остаток от 12 / 6 = 0 → НОД(6, 0)
b = 0, значит ответ 6

Разбор

Главная программа

алг
нач
    вывод "НОД(48, 18) = ", нод(48, 18), нс
кон

Функция нод

алг цел нод(цел a, цел b)
нач
    цел x, y, t
    x := a
    y := b
    нц пока y <> 0
        t := y
        y := mod(x, y)
        x := t
    кц
    знач := x
кон

Параметры a и b менять нельзя (это аргументы), поэтому работаем с их копиями x и y
нц пока y <> 0 — цикл продолжается, пока y не равно нулю (<> означает «не равно»)
mod(x, y) — остаток от деления x на y
Переменная t нужна, чтобы временно сохранить значение y перед заменой
Когда y становится 0, в x лежит ответ — возвращаем его через знач

Полная программа

алг
нач
    вывод "НОД(48, 18) = ", нод(48, 18), нс
кон

алг цел нод(цел a, цел b)
нач
    цел x, y, t
    x := a
    y := b
    нц пока y <> 0
        t := y
        y := mod(x, y)
        x := t
    кц
    знач := x
кон