DEV//UNIT
← Алгоритмыmath

НОД (алгоритм Евклида)

НОД двух чисел через остатки: a mod b, пока не ноль.

время O(log min(a,b))память O(1)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function gcd(a: number, b: number): number {
2  while (b !== 0) {
3    const t = a % b
4    a = b
5    b = t
6  }
7  return a
8}

Проблема

НОД двух чисел через остатки: a mod b, пока не ноль.

Что вы видите

Пары (a,b) уменьшаются: 48 и 18 → 18 и 12 → 12 и 6 → 6 и 0.

Как это работает

НОД(a,b) = НОД(b, a mod b): любой общий делитель a и b делит и остаток. Остатки строго убывают — за логарифм шагов доходим до нуля.

Пошаговый разбор

  1. 01

    Остаток

    a mod b.

  2. 02

    Замена

    a←b, b←остаток.

  3. 03

    Ноль

    b=0 — ответ a.

Complexity и ограничения

time
O(log min(a,b))
space
O(1)

Сложность см. в шапке страницы.

Edge cases

  • Пустой вход

    Корректная тривиальная обработка.

  • Вырожденный случай

    Минимум работы — сразу ответ.

Где встречается в реальности

Дроби

Сокращение дробей на НОД.

RSA

Модульная арифметика, обратные по модулю.

Расписания

Пересечение периодических событий через НОК.

Связанные алгоритмы

Хеш-таблицаРешето Эратосфена
Shorts

«Древнейший алгоритм — 2300 лет в строю»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Древнейший алгоритм — 2300 лет в строю
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/gcd