Как находят НОД
НОД — наибольшее число, на которое делятся все введённые числа без остатка. Используется алгоритм Евклида: большее число заменяется остатком от деления на меньшее, пока остаток не станет нулём.
Для 12 и 18: 18 mod 12 = 6, затем 12 mod 6 = 0, значит НОД равен 6. Для нескольких чисел НОД считается последовательно: НОД(a, b, c) = НОД(НОД(a, b), c).
Как находят НОК
НОК — наименьшее число, которое делится на все введённые. Связь с НОД простая: НОК(a, b) = a ÷ НОД(a, b) × b. Деление выполняется первым, чтобы не получить слишком большое промежуточное произведение.
Для 12 и 18 НОК равен 36. Для трёх и более чисел НОК тоже считается последовательно, пара за парой.
Где это нужно
НОД используется для сокращения дробей: разделите числитель и знаменатель на их НОД — получите несократимый вид. Это делает и калькулятор дробей.
НОК нужен для приведения дробей к общему знаменателю и в задачах на совпадение циклов: через сколько минут снова встретятся автобусы с разными интервалами.
Методика и источники
Проверка реализации: . Как проверяются вычисления.
Формула и допущения приведены выше; контрольные примеры включены в автоматические проверки проекта.