Как пользоваться
- Введите от 2 до 20 целых чисел, каждое меньше триллиона (10¹²), через запятую, пробел или с новой строки.
- НОД и НОК появятся сразу, ниже — алгоритм Евклида и разложение на простые множители.
Как считается
Алгоритм Евклида. Для двух чисел a > b записываем a = q × b + r и продолжаем с b и r, пока остаток не станет нулём. Последний делитель — НОД.
Через простые множители. НОД — произведение общих множителей в наименьших степенях, НОК — всех множителей в наибольших степенях. Для двух чисел есть короткая формула: НОК(a, b) = a × b ÷ НОД(a, b).
НОК считается точно, в целых числах, поэтому даже НОК из нескольких десятков цифр не округляется.
Пример
84, 120 и 36:
- Алгоритм Евклида: 120 = 1 × 84 + 36, 84 = 2 × 36 + 12, 36 = 3 × 12 + 0, значит НОД(84, 120) = 12; затем 36 = 3 × 12 + 0 — НОД всех трёх чисел равен 12.
- Разложение: 84 = 2² × 3 × 7, 120 = 2³ × 3 × 5, 36 = 2² × 3².
- НОД = 2² × 3 = 12, НОК = 2³ × 3² × 5 × 7 = 2520.
Где пригодится
- Дроби. На НОД сокращают дробь (84/120 = 7/10 после деления на 12), а НОК знаменателей — это наименьший общий знаменатель.
- Расписания. Автобусы, которые ходят каждые 12 и 18 минут, снова отправятся одновременно через НОК(12, 18) = 36 минут.
- Раскрой. Самая большая квадратная плитка, которая ровно ложится на площадку 84 × 120 см, — со стороной НОД = 12 см.