Как найти простые множители: разложение по шагам

Дано: число $N = 51\,912$. Найти: каноническое разложение на простые множители и число делителей.

Метод один: перебираем делители по возрастанию, а границу перебора берём не от исходного числа, а от текущего остатка, и она падает после каждого удачного деления. Ответ: $51\,912 = 2^3 \cdot 3^2 \cdot 7 \cdot 103$, делителей у числа 48. Калькулятор сверху проходит ту же лестницу для любого числа до миллиарда, а ниже разбор по шагам.

Решение по шагам

Дано. $N = 51\,912$. Найти: запись вида $p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ и число делителей $\tau(N)$.

Шаг 1. Оцениваем, до какого числа перебирать. Считаем корень: $\sqrt{51\,912} \approx 227{,}8$. Значит наименьший нетривиальный делитель лежит в промежутке от 2 до 227, и выходить за эту границу не нужно.

Шаг 2. Вычерпываем двойки. Число чётное, делим на 2, пока делится:

$$51\,912 : 2 = 25\,956, \qquad 25\,956 : 2 = 12\,978, \qquad 12\,978 : 2 = 6489.$$

Число 6489 нечётное, двойки кончились. В разложение уходит $2^3$: важно вынести всю степень сразу, а не одну двойку.

Шаг 3. Вычерпываем тройки. Сумма цифр числа 6489 равна $6 + 4 + 8 + 9 = 27$, она делится на 9, поэтому тройка вынесется как минимум дважды:

$$6489 : 3 = 2163, \qquad 2163 : 3 = 721.$$

У числа 721 сумма цифр равна 10, на 3 оно уже не делится. Получили $3^2$.

Шаг 4. Работаем с остатком 721. Здесь начинается главная экономия: граница перебора пересчитывается по остатку, а не по исходному числу. Теперь она равна $\sqrt{721} \approx 26{,}9$, то есть вместо двух с лишним сотен кандидатов осталось меньше тридцати. Число 721 не оканчивается на 0 или 5, значит пятёрка отпадает; пробуем семёрку:

$$721 : 7 = 103.$$

Шаг 5. Проверяем остаток 103 на простоту. Граница снова падает: $\sqrt{103} \approx 10{,}1$, и проверить достаточно 2, 3, 5 и 7. Число нечётное, сумма цифр 4, на 0 или 5 не оканчивается, а $103 = 7 \cdot 14 + 5$. Ни один кандидат не подошёл, следующее простое число 11 даёт $11^2 = 121 > 103$, и перебор закончен: 103 простое, вынимаем его целиком.

Шаг 6. Собираем каноническую запись. Выписываем найденные множители в порядке возрастания со степенями:

$$51\,912 = 2^3 \cdot 3^2 \cdot 7 \cdot 103.$$

Проверка обратным умножением обязательна и занимает одну строку: $8 \cdot 9 = 72$, затем $72 \cdot 7 = 504$ и $504 \cdot 103 = 51\,912$. Сошлось.

Шаг 7. Считаем число делителей. Каждый показатель увеличиваем на единицу и перемножаем:

$$\tau(N) = (3 + 1)(2 + 1)(1 + 1)(1 + 1) = 4 \cdot 3 \cdot 2 \cdot 2 = 48.$$

Ответ: $51\,912 = 2^3 \cdot 3^2 \cdot 7 \cdot 103$, число делителей равно 48. Всего понадобилось 15 проверок делимости, тогда как перебор всех чисел до половины исходного потребовал бы 25 955 проверок.

Формула: почему хватает делителей до корня

Пусть число $N$ составное, то есть представимо в виде $N = a \cdot b$, где оба множителя больше единицы. Один из них обязательно не превосходит корня: если бы одновременно $a > \sqrt{N}$ и $b > \sqrt{N}$, то произведение было бы больше $N$, чего быть не может. Отсюда рабочее правило:

$$\text{наименьший делитель } d > 1 \ \text{ числа } N \ \text{ удовлетворяет } \ d \leqslant \sqrt{N}.$$

Дальше нужно заметить, что этот наименьший делитель обязательно прост. Будь он составным, у него нашёлся бы собственный делитель поменьше, который делил бы и само $N$, а мы взяли самый маленький. Поэтому перебор снизу вверх выдаёт именно простые множители и ничего лишнего.

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

Второй важный нюанс касается того, что именно стоит под корнем. Граница пересчитывается для текущего остатка, а не для исходного числа: в разборе она прошла путь 227, затем 26,9 и наконец 10,1. Именно поэтому разложение шестизначного числа укладывается в полтора десятка проверок.

Наконец, перебирать можно все целые числа подряд, а не только простые, и ответ от этого не испортится. Когда очередь доходит до 4, все двойки из остатка уже вынуты, поэтому четвёрка разделить его не сможет; то же с 6, 8, 9 и любым другим составным кандидатом. Таблица простых чисел ускоряет счёт, но для корректности не обязательна.

Число делителей из показателей

Формула $\tau(N) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$ выглядит как трюк, хотя доказывается в одну фразу. Любой делитель числа $N$ строится только из тех же простых множителей и только в тех же или меньших степенях:

$$d = 2^{b_1} \cdot 3^{b_2} \cdot 7^{b_3} \cdot 103^{b_4}, \qquad 0 \leqslant b_1 \leqslant 3, \quad 0 \leqslant b_2 \leqslant 2, \quad 0 \leqslant b_3, b_4 \leqslant 1.$$

Показатели выбираются независимо друг от друга, поэтому вариантов ровно $4 \cdot 3 \cdot 2 \cdot 2 = 48$, и каждый набор даёт свой, ни с чем не совпадающий делитель. Нулевые показатели тоже считаются: они дают единицу и само число.

Тем же способом собираются ещё две школьные величины. Сумма всех делителей получается перемножением сумм степеней каждого простого:

$$\sigma(N) = (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 7)(1 + 103) = 15 \cdot 13 \cdot 8 \cdot 104 = 162\,240,$$

а количество чисел, взаимно простых с $N$ и не превосходящих его, равно $\varphi(N) = 4 \cdot 6 \cdot 6 \cdot 102 = 14\,688$. Все три функции мультипликативны, то есть считаются по множителям независимо, и в этом же ряду стоит функция Мёбиуса, которая различает разложения со степенями и без. Именно поэтому ответ принято записывать канонически, со степенями, а не длинной цепочкой повторяющихся множителей.

Где перебор перестаёт работать

Число проверок растёт как корень из числа, то есть примерно вдвое медленнее его длины в цифрах. Для шестизначного числа корень - это три сотни кандидатов, для двадцатизначного уже десять миллиардов, а для ключа RSA на 617 цифр перебор бессмысленен: никакой техники не хватит. При этом проверить число на простоту гораздо дешевле, чем разложить его, и вероятностные тесты делают это через возведение в степень по модулю, разобранное в задаче как быстро возвести в степень.

На этом разрыве и держится вся криптография с открытым ключом: перемножить два больших простых легко, а восстановить их из произведения нечем. Квантовый выход из положения существует, но лишь теоретический, и разобран он в статье про алгоритм Шора. Для учебных чисел до миллиона школьный перебор остаётся самым быстрым по времени решения способом.

Частые ошибки

• Перебирают делители до половины числа. Для 51 912 это 25 955 проверок вместо 15. Граница перебора - корень, и она обоснована, а не выбрана для скорости.
• Не пересчитывают границу после каждого деления. Корень надо брать от текущего остатка: после выноса двоек и троек проверять кандидатов до 227 уже не нужно, хватает 26.
• Выносят простой множитель один раз. Из 51 912 двойка вынимается трижды. Если остановиться на первом делении, произведение множителей не даст исходное число, и обратная проверка это сразу покажет.
• Объявляют остаток простым раньше времени. Число 721 нечётное, не делится ни на 3, ни на 5 и выглядит простым, но $721 = 7 \cdot 103$. Проверку надо доводить до корня, а не бросать после трёх кандидатов.
• Перемножают показатели вместо увеличенных на единицу. Ответ $3 \cdot 2 \cdot 1 \cdot 1 = 6$ вместо 48 получается именно так. Показатель $a$ даёт $a + 1$ вариантов, потому что нулевая степень тоже разрешена.
• Вписывают единицу в разложение. Единица не простое число, множителем её не пишут; на число делителей она никак не влияет.

FAQ

Почему достаточно проверять делители только до квадратного корня? Потому что делители ходят парами: если $N = a \cdot b$, то один из множителей не больше $\sqrt{N}$, а второй не меньше. Найдя все делители до корня, парные к ним мы получаем делением и ничего не теряем.

Обязательно ли перебирать только простые числа? Нет. Составной кандидат никогда не разделит остаток, потому что его собственные простые множители вынуты раньше. Перебор по простым просто короче: для 51 912 это 10 проверок вместо 15.

Как понять, что оставшийся остаток простой? Если ни одно число от 2 до корня из остатка его не делит, остаток прост. В разборе так закрылось число 103: проверили 2, 3, 5 и 7, а $11^2 = 121$ уже больше 103, поэтому перебор остановлен.

Чем каноническое разложение лучше простого перечисления множителей? Записью со степенями. Из показателей мгновенно считаются число делителей, их сумма и функция Эйлера, а также наибольший общий делитель и наименьшее общее кратное двух чисел. Список вида 2, 2, 2, 3, 3, 7, 103 всё это скрывает.

Коротко

1. Оцени границу перебора: $\sqrt{51\,912} \approx 227{,}8$, значит наименьший делитель ищем среди чисел от 2 до 227.
2. Вычерпывай простые по возрастанию, каждое до конца: $2^3$, затем $3^2$, затем 7.
3. После каждого деления пересчитывай границу по остатку: она упала с 227 до 26,9, а потом до 10,1.
4. Остаток без делителей до своего корня прост: число 103 вынимается целиком, и разложение готово: $51\,912 = 2^3 \cdot 3^2 \cdot 7 \cdot 103$.
5. Проверь обратным умножением ($504 \cdot 103 = 51\,912$) и посчитай делители по показателям: $\tau = 4 \cdot 3 \cdot 2 \cdot 2 = 48$.