Что считает этот калькулятор
Этот инструмент находит две ключевые величины из теории чисел для любого списка из двух и более целых чисел: наибольший общий делитель (НОД) и наименьшее общее кратное (НОК). В англоязычных источниках НОД называют GCD, GCF или HCF — это одно и то же. НОД — это самое большое положительное число, на которое без остатка делится каждое из введённых чисел. НОК — наименьшее положительное число, которое без остатка делится на каждое из них. Эти понятия встречаются повсюду: от сокращения дробей и приведения их к общему знаменателю до составления расписаний, расчёта передаточных чисел в шестернях и криптографии.
Как пользоваться
Введите два и более целых положительных числа через запятую или пробел, например 12, 18, 24, и нажмите «Рассчитать». Отрицательные числа берутся по модулю, а дробные округляются до ближайшего целого. Калькулятор сразу выдаёт и НОД, и НОК. Если хотя бы одно из чисел равно нулю, НОК принимается равным 0 — ведь у нуля нет общих положительных кратных с другими числами.
Как работает формула
Для двух чисел НОД вычисляется по алгоритму Евклида: пару \((a, b)\) раз за разом заменяют на \((b, a \bmod b)\), пока второе число не станет равно 0; оставшееся первое число и есть НОД. НОК затем находят по формуле
$$\operatorname{lcm}(a,b) = \frac{a}{\gcd(a,b)} \times b$$— именно в таком порядке, чтобы избежать переполнения при больших значениях. Для трёх и более чисел результат собирают попарно: текущий ответ объединяют со следующим числом, затем со следующим и так далее.
$$\gcd(a_1,\dots,a_k), \qquad \operatorname{lcm}(a_1,\dots,a_k) = \frac{|a_i \cdot a_j|}{\gcd(a_i,a_j)}$$где
$$\left\{ \begin{aligned} a_1,\dots,a_k &= \text{Integers (abs. values)} \\ \gcd &= \text{computed via the Euclidean algorithm} \end{aligned} \right.$$
Разбор примера
Возьмём 12, 18, 24. Сначала \(\gcd(12, 18) = 6\), затем \(\gcd(6, 24) = 6\), значит НОД равен 6. Теперь НОК:
$$\operatorname{lcm}(12, 18) = \frac{12 \times 18}{6} = 36$$потом
$$\operatorname{lcm}(36, 24) = \frac{36 \times 24}{12} = 72$$то есть НОК равен 72. Проверим: \(72 \div 12 = 6\), \(72 \div 18 = 4\), \(72 \div 24 = 3\), а 6 действительно делит все три исходных числа.
Частые вопросы
НОД и НОК — это разные вещи? Да. НОД (наибольший общий делитель) — самое большое число, на которое делятся все аргументы; НОК (наименьшее общее кратное) — наименьшее число, которое делится на все аргументы. В английских материалах НОД обозначают как GCD, GCF или HCF — это всё одно и то же число.
Что, если у чисел нет общих делителей? Если НОД равен 1, числа называются взаимно простыми, а их НОК — это просто произведение всех чисел.
Можно ли вводить больше двух чисел? Да. Вводите сколько угодно целых чисел — НОД и НОК будут рассчитаны для всего списка сразу.
