Наибольший общий делитель в JavaScript: алгоритмы и код

[hannadev]

Наибольший общий делитель (НОД) - это базовая математическая операция, которая часто нужна в программировании. В JavaScript её реализуют для упрощения дробей, оптимизации алгоритмов или работы с числами. Мы разберём, как вычислить НОД для двух чисел и массива, используя простые методы.

Это полезно для задач с факторизацией, генерацией последовательностей или обработки данных. Вы узнаете алгоритм Евклида, циклы и рекурсию, с готовыми примерами кода. Такие знания помогут избежать ошибок в проектах и ускорить вычисления.

Что такое НОД и зачем он в JavaScript

НОД двух чисел - это наибольшее число, на которое оба делятся без остатка. Например, для 48 и 18 НОД равен 6, потому что 48 / 6 = 8 и 18 / 6 = 3. В JavaScript это решают алгоритмом Евклида: берём остаток от деления и повторяем, пока делитель не станет нулевым.

Алгоритм работает быстро даже для больших чисел, O(log n) операций. Без него пришлось бы перебирать делители вручную, что медленно. В реальных задачах НОД используют для сокращения дробей в графике или расчёта НОК - наименьшего общего кратного.

Вот базовые свойства НОД:

• НОД(a, b) = НОД(b, a)
• НОД(a, 0) = |a|
• НОД(a, b) = НОД(b, a % b)

Свойство	Пример	Результат
Коммутативность	НОД(12, 18)	6
Нулевой делитель	НОД(15, 0)	15
Рекурсия	НОД(48, 18) = НОД(18, 12)	6

Реализация НОД через цикл while

Метод с циклом - самый простой для понимания. Функция принимает два числа, берёт их абсолютные значения и в цикле заменяет делимое на делитель, а делитель на остаток. Цикл продолжается, пока второй аргумент не обнулится.

Рассмотрим код: сначала сохраняем b в temp, потом b = a % b, a = temp. Это стандартная реализация Евклида. Для отрицательных чисел используем Math.abs(), чтобы НОД всегда был положительным. Тестируем на примерах: gcd(48, 18) вернёт 6, gcd(7, 13) - 1.

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

• Плюсы цикла: Не переполняет стек рекурсии, работает с большими числами.
• Минус: Чуть больше строк кода, чем в рекурсии.
• Пример вызова: console.log(gcd(100, 25)); // 25

Рекурсивный подход к НОД

Рекурсия делает код короче: функция вызывает себя с новыми аргументами до базы случая. База - когда b равно 0, возвращаем a. Это элегантный вариант Евклида, популярный в учебниках.

Для нескольких чисел редуцируем задачу: сначала НОД первых двух, потом с третьим и так далее. В ECMAScript 2022 есть встроенный BigInt.gcd, но для простоты напишем свой. Пример: gcd(9, 12) -> gcd(12, 9 % 12=9) -> gcd(9, 12 % 9=3) -> gcd(3, 9 % 3=0) -> 3.

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  if (b === 0) return a;
  return gcd(b, a % b);
}

// Для массива
function gcdArray(nums) {
  return nums.reduce((acc, num) => gcd(acc, num));
}

• Преимущества: Код лаконичный, легко читать.
• Ограничение: Глубокая рекурсия может вызвать ошибку стека.
• Тест: gcdArray([48, 18, 36]) // 6

Метод	Код строк	Скорость	Подходит для
Цикл	8	Быстро	Большие числа
Рекурсия	4	Быстро	Малые глубины
Встроенный	1	Оптимально	Современный JS

Расширение на диапазон и массив чисел

Иногда нужно найти НОД всех чисел в диапазоне [L, R], как в задачах с GitHub-проектами. Проходим циклом по диапазону и обновляем текущий НОД. Для массивов используем reduce - встроенный метод, который накапливает результат.

Оптимизация: если НОД стал 1, дальше искать бессмысленно. В реальных проектах это ускоряет обработку больших массивов. Пример для [1,5]: НОД(1,2,3,4,5)=1. Для [10,20]: НОД=10.

function gcdRange(L, R) {
  let result = L;
  for (let i = L + 1; i <= R; i++) {
    result = gcd(result, i);
    if (result === 1) break;
  }
  return result;
}

• Диапазон [4,8]: gcd=4
• Нюанс: Для L=1 всегда 1.
• Массив: [24,36,48] -> 12

Практические трюки с НОД в проектах

НОД упрощает дроби: 48/18 сократить до 8/3. В графике генерирует уникальные цвета через НОК. Для НОК используйте формулу: НОК(a,b) = (a * b) / gcd(a,b), но осторожно с переполнением.

В MDN показывают, как добавить Math.gcd для вариативных аргументов. Это удобно для массивов без reduce. Тестируйте на edge-кейсах: нули, отрицательные, 1. Такие функции пишут в утилитах для повторного использования.

Ключевые трюки:

• Всегда берите Math.abs() для отрицательных.
• Избегайте деления на ноль проверкой.
• Для BigInt в Node.js используйте BigInt(a) % BigInt(b).

Вариации НОД для продвинутых задач

НОД работает не только с парами, но и с трёхмерными векторами в геймдеве или криптографии. Связан с алгоритмом Стерлинга для факториалов. В асинхронном коде оборачивайте в Web Workers для тяжёлых расчётов.

Осталось место для оптимизаций вроде бинарного ГCD - быстрее на 20-30% за счёт сдвигов бит. Или комбинация с Math - для дробей в Canvas. Подумать стоит над интеграцией в React/Vue компоненты для интерактивных калькуляторов.