Как это работает
Наибольший общий делитель (НОД) вычисляется алгоритмом Евклида: большее число заменяют остатком от его деления на меньшее, пока остаток не станет равен 0. Для трёх и более чисел шаг повторяется попарно.
Наименьшее общее кратное (НОК) получается из НОД: НОК(a, b) = |a × b| ÷ НОД(a, b), тоже попарно. Все вычисления идут в точных целых числах, поэтому даже 30-значные числа дают точный результат.
Алгоритм Евклида по шагам
Пример для 1071 и 462: в каждой строке предыдущий делитель делится на остаток, а последний ненулевой остаток и есть НОД.
- 1071 = 2 × 462 + 147
- 462 = 3 × 147 + 21
- 147 = 7 × 21 + 0 → gcd = 21
gcd(a, b) = gcd(b, a mod b) · lcm(a, b) = |a × b| ÷ gcd(a, b)
Где это нужно
- НОД: сократить дробь — 18/24 после деления на НОД 6 превращается в 3/4.
- НОК: найти общий знаменатель или момент, когда повторяющиеся события снова совпадут (каждые 4 и каждые 6 дней → каждые 12 дней).
- НОД: разделить плитку, ряды или группы на равные части без остатка.
Советы
- Два числа взаимно просты, если их НОД равен 1; при этом оба могут быть составными, как 8 и 9.
- Для двух положительных чисел НОД(a, b) × НОК(a, b) = a × b — удобная проверка.
- Ноль допустим: НОД(a, 0) = a, но любое НОК с нулём равно 0.
Стандарты и источники
- Алгоритм Евклида · NIST Dictionary of Algorithms and Data Structures
- Наименьшее общее кратное · NIST Dictionary of Algorithms and Data Structures
Последняя проверка 20 октября 2026 г.
Часто задаваемые вопросы
Чем НОД отличается от НОК?
НОД — наибольшее число, на которое делятся все числа; НОК — наименьшее число, которое делится на все. Для 12 и 18 НОД равен 6, а НОК — 36.
НОД — это то же, что GCD или HCF?
Да. GCD, GCF и HCF — английские названия того же наибольшего общего делителя.
Сколько чисел можно ввести?
Сколько угодно; НОД и НОК считаются попарно. Простые множители показываются для первых 12 чисел.