Что такое алгоритм Евклида

Что проверяют

Базовую алгоритмическую грамотность и аккуратность в реализации. Фронтендеру наибольший общий делитель нужен реже, чем бэкендеру, но задача всплывает при сокращении дробей, в расчёте соотношения сторон и просто как разминка на живом кодировании.

Как отвечать

Алгоритм ищет наибольший общий делитель двух целых чисел и опирается на то, что делитель пары не меняется, если большее число заменить остатком от деления на меньшее. Повторяем, пока остаток не станет нулём: последнее ненулевое значение и есть ответ.

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

Скажите про сложность: число шагов логарифмично от меньшего аргумента, худший случай это пара соседних чисел Фибоначчи. Для значений за пределами безопасного целого в JavaScript берут BigInt, код остаётся тем же с точностью до литерала нуля.

Продолжения, которые обычно и спрашивают: наименьшее общее кратное считается через делитель, причём делить надо до умножения, иначе промежуточное произведение вылетит из безопасного диапазона; расширенный вариант дополнительно возвращает коэффициенты, через которые находят обратный элемент по модулю.

Где спотыкаются

Реализуют вычитательный вариант и на паре из единицы и миллиарда получают миллиард итераций. Остаток от деления делает ту же работу за логарифмическое число шагов.

Не обрабатывают знак и ноль. В JavaScript остаток наследует знак делимого, поэтому без взятия модуля функция вернёт отрицательное значение; отдельно стоит проговорить, что делитель нуля и числа равен этому числу.

Пишут рекурсию и забывают, что аргументы обязаны быть целыми. Дробное значение или строка из поля ввода уводят цикл в бесконечность либо дают NaN, поэтому приведение и проверка делаются до входа в цикл.