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

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

НОД — это самое большое число, на которое оба числа делятся без остатка. Например, НОД(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)
нач
    нц пока b <> 0
        цел t
        t := b
        b := mod(a, b)
        a := t
    кц
    знач := a
кон

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

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

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

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