Что делает этот калькулятор
Инструмент принимает набор из двух или более целых положительных чисел и находит сразу три вещи: полный список делителей каждого числа, общие делители для всех чисел и наибольший общий делитель (НОД). Это пригодится при сокращении дробей, разложении выражений на множители и решении домашних заданий по теории чисел. В русскоязычной литературе используется аббревиатура НОД, тогда как в английских источниках вы встретите обозначения GCF (greatest common factor) и GCD (greatest common divisor) — это одно и то же.
Как пользоваться
Введите целые числа через запятую, например 136, 64, 24, 16, и сразу получите результат. Для каждого числа делители выводятся по возрастанию, затем показываются общие делители и единственное значение НОД. Используйте только целые положительные числа: ноль, отрицательные значения и дроби в качестве делителей не подходят.
Как это считается
Целое число d является делителем числа n, если \(n \bmod d = 0\) (то есть деление выполняется без остатка). Чтобы быстро найти все делители, мы перебираем i от 1 до квадратного корня из n: как только i делит n, делителями сразу являются и i, и \(n/i\). НОД для списка вычисляется попарно по алгоритму Евклида: пока b не равно нулю, заменяем пару (a, b) на (b, a mod b); оставшееся значение a и есть НОД. Формально:
$$\gcd(a, 0) = a, \quad \gcd(a, b) = \gcd(b, \; a \bmod b)$$
Полезный факт: общие делители всего набора — это в точности делители самого НОД:
$$\text{CommonFactors} = \{\, d : g \bmod d = 0 \,\}, \quad g = \gcd(n_1, n_2, \dots)$$
Разбор примера
Возьмём числа 136, 64, 24, 16. Делители 16: 1, 2, 4, 8, 16; делители 24: 1, 2, 3, 4, 6, 8, 12, 24; делители 64: 1, 2, 4, 8, 16, 32, 64; делители 136: 1, 2, 4, 8, 17, 34, 68, 136. По алгоритму Евклида: \(\gcd(16, 24) = 8\), затем \(\gcd(8, 64) = 8\), затем \(\gcd(8, 136) = 8\) — значит, НОД = 8. Делители числа 8: 1, 2, 4, 8 — это и есть общие делители всего набора.
Частые вопросы
НОД и GCD — это одно и то же? Да. Наибольший общий делитель (НОД), greatest common factor (GCF) и greatest common divisor (GCD) — это разные названия одной и той же величины.
А если у чисел нет общих делителей? У любого набора целых положительных чисел есть общий делитель 1, поэтому множество общих делителей всегда содержит как минимум \(\{1\}\), а НОД не меньше 1. Числа, у которых единственный общий делитель — это 1, называют взаимно простыми.
Можно ввести только одно число? Да — тогда выводятся его делители, а НОД равен самому этому числу.
