Как найти все делители числа

Что такое делитель числа: базовые понятия

В арифметике и теории чисел делителем целого числа $n$ называют такое целое число $m$, на которое исходное число $n$ делится без остатка. В таком случае говорят, что $n$ кратно $m$.

Например, для числа $12$ делителями будут $1, 2, 3, 4, 6$ и $12$. Если вы попробуете разделить $12$ на любое другое число (скажем, на $5$), то получите дробное значение ($2.4$), а значит, $5$ не является его делителем.

Каждое натуральное число (за исключением единицы) имеет как минимум два делителя: единицу и самого себя. Такие делители называют тривиальными. Если у числа больше нет других делителей, оно называется простым. Если другие делители есть, число называют составным.

Метод 1. Поиск делителей через пары (до квадратного корня)

Самый быстрый и эффективный способ найти все делители числа вручную — это метод парного перебора. Он основан на простом свойстве: у каждого делителя $a$ есть парный делитель $b$, такой что $a \times b = n$.

Чтобы не перебирать все числа подряд до самого $n$, достаточно дойти только до квадратного корня из этого числа ($\sqrt{n}$). Это экономит огромное количество времени.

Алгоритм поиска:

1. Вычислите приближенный квадратный корень из числа $n$.
2. Начните последовательно проверять деление на числа от $1$ до полученного значения.
3. Если число делится без остатка, запишите в таблицу сразу два делителя: делитель (на что делили) и частное (результат деления).
4. Округлите шаг и прекратите перебор, когда перейдете границу квадратного корня.
5. Упорядочите полученный список по возрастанию.

Пример: найдем делители числа 60

Квадратный корень из $60$ находится между целыми числами $7$ и $8$ ($\sqrt{60} \approx 7.74$). Значит, нам нужно проверить делимость только на числа от $1$ до $7$.

Все числа больше $7$ проверять не нужно — их пары уже найдены на предыдущих шагах.
Ответ: Делителями числа $60$ являются: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.

Метод 2. Разложение на простые множители (факторизация)

Этот метод идеально подходит для больших чисел, когда обычный перебор занимает слишком много времени. Он базируется на Основной теореме арифметики: любое составное число можно представить в виде произведения простых чисел, причем единственным способом.

Алгоритм поиска:

1. Разложите число на простые множители (делением на минимально возможные простые числа: $2, 3, 5, 7, 11$ и т. д.).
2. Выпишите все уникальные простые множители.
3. Перемножьте эти множители между собой во всех возможных комбинациях.
4. Добавьте к результатам единицу.

Пример: найдем все делители числа 45

Разложим число $45$ на простые сомножители:

• $45 : 3 = 15$
• $15 : 3 = 5$
• $5 : 5 = 1$

Каноническое разложение имеет вид:
$45 = 3 \times 3 \times 5 = 3^2 \times 5^1$

Теперь комбинируем полученные простые множители ($3, 3, 5$):

• Базовые множители (без повторов): $3$ и $5$.
• Произведения парных комбинаций: $3 \times 3 = 9$, $3 \times 5 = 15$.
• Произведение трех множителей: $3 \times 3 \times 5 = 45$.
• Добавляем обязательную единицу: $1$.

Объединяем все уникальные значения в единый список по возрастанию:
Ответ: 1, 3, 5, 9, 15, 45.

Как узнать общее количество делителей без их поиска

Иногда перед нами стоит задача определить не сами делители, а лишь их точное количество. Для этого существует простая и элегантная математическая формула.

Если разложение числа $n$ на простые множители выглядит как: $n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$ где $p$ — простые множители, а $a$ — их степени, то общее количество делителей $N$ вычисляется по формуле: $N = (a_1 + 1) \times (a_2 + 1) \times \dots \times (a_k + 1)$

Пример расчета

Возьмем то же число $60$. Его представление в виде степеней простых чисел:
$60 = 2^2 \times 3^1 \times 5^1$

Показатели степеней равны: $a_1 = 2$, $a_2 = 1$, $a_3 = 1$.
Подставим эти показатели в формулу: $N = (2 + 1) \times (1 + 1) \times (1 + 1) = 3 \times 2 \times 2 = 12$

Мы получили ровно $12$ делителей, что полностью совпадает с нашими практическими вычислениями в предыдущем разделе.

Классификация чисел по типу их делителей

В зависимости от суммы и характера собственных делителей (всех делителей числа, за вычетом его самого), числа делят на несколько категорий:

• Совершенные числа. Числа, которые равны сумме всех своих собственных делителей. Пример: для числа $6$ собственные делители — $1, 2, 3$. Их сумма: $1 + 2 + 3 = 6$.
• Избыточные числа. Числа, сумма собственных делителей которых превышает само число. Пример: собственные делители числа $12$ — это $1, 2, 3, 4, 6$. Их сумма равна $16$, что больше $12$.
• Недостаточные числа. Числа, у которых сумма собственных делителей оказывается меньше самого исходного числа. Сюда относятся все простые числа, а также многие составные (например, собственные делители числа $8$ равны $1, 2, 4$, а их сумма равна всего лишь $7$).