Все делители числа

Теория

Делители числа \(n\) — все натуральные числа, на которые \(n\) делится без остатка. Любой делитель \(d\) имеет пару: частное \(n/d\) — тоже делитель. Поэтому перебор можно вести только до \(\sqrt{n}\), дополняя каждый найденный делитель его парой.

Количество делителей легко сосчитать по разложению на простые множители. Если \(n = p_1^{k_1} \times p_2^{k_2} \times \ldots\), то делителей \((k_1 + 1)(k_2 + 1)\ldots\): каждый множитель может входить в делитель в степени от 0 до \(k_i\).

Важно: единица и само число — тоже делители, их включают в список всегда.

Пример с решением

1. Условие. Найдите все делители числа 12.
2. Формула. Перебор \(d\) от 1 до \(\sqrt{n}\) с добавлением парного делителя \(n/d\).
3. Подстановка. \(\sqrt{12} \approx 3{,}46\), проверяем 1, 2, 3.
4. Вычисление. 1 → пара 12; 2 → пара 6; 3 → пара 4. Список: 1, 2, 3, 4, 6, 12.
5. Ответ. Делители 12: 1, 2, 3, 4, 6, 12 — всего 6. Проверка по формуле: \(12 = 2^2 \times 3\), делителей \((2+1)(1+1) = 6\). Калькулятор с полем 12 выдаст тот же список.

Главное

• Перебор до \(\sqrt{n}\) с парными делителями \(n/d\).
• Количество делителей: \((k_1+1)(k_2+1)\ldots\) по разложению на простые.
• 1 и само число — всегда делители.