Как найти все делители числа
Узнайте, как быстро найти все делители натурального числа вручную и с помощью алгоритмов. Простые методы, наглядные примеры и свойства делителей.
Что такое делитель числа: базовые понятия
В арифметике и теории чисел делителем целого числа $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}$). Это экономит огромное количество времени.
Алгоритм поиска:
- Вычислите приближенный квадратный корень из числа $n$.
- Начните последовательно проверять деление на числа от $1$ до полученного значения.
- Если число делится без остатка, запишите в таблицу сразу два делителя: делитель (на что делили) и частное (результат деления).
- Округлите шаг и прекратите перебор, когда перейдете границу квадратного корня.
- Упорядочите полученный список по возрастанию.
Пример: найдем делители числа 60
Квадратный корень из $60$ находится между целыми числами $7$ и $8$ ($\sqrt{60} \approx 7.74$). Значит, нам нужно проверить делимость только на числа от $1$ до $7$.
| Проверяемое число | Делится ли без остатка? | Найдено делителей (пара) |
|---|---|---|
| 1 | Да ($60 : 1 = 60$) | $1$ и $60$ |
| 2 | Да ($60 : 2 = 30$) | $2$ и $30$ |
| 3 | Да ($60 : 3 = 20$) | $3$ и $20$ |
| 4 | Да ($60 : 4 = 15$) | $4$ и $15$ |
| 5 | Да ($60 : 5 = 12$) | $5$ и $12$ |
| 6 | Да ($60 : 6 = 10$) | $6$ и $10$ |
| 7 | Нет ($60 : 7 = 8.57…$) | — |
Все числа больше $7$ проверять не нужно — их пары уже найдены на предыдущих шагах.
Ответ: Делителями числа $60$ являются: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.
Метод 2. Разложение на простые множители (факторизация)
Этот метод идеально подходит для больших чисел, когда обычный перебор занимает слишком много времени. Он базируется на Основной теореме арифметики: любое составное число можно представить в виде произведения простых чисел, причем единственным способом.
Алгоритм поиска:
- Разложите число на простые множители (делением на минимально возможные простые числа: $2, 3, 5, 7, 11$ и т. д.).
- Выпишите все уникальные простые множители.
- Перемножьте эти множители между собой во всех возможных комбинациях.
- Добавьте к результатам единицу.
Пример: найдем все делители числа 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$).