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

Введите число — решатель разложит его на простые множители по шагам, построит дерево множителей, найдёт все делители и проверит ответ.

Примеры: 360 1001 97 делители 360 2^32 + 1 600 851 475 143 10!

Загружаем решатель…

Что можно ввести

Любое натуральное число до шестидесяти цифр: 360, 600 851 475 143 (пробелы между тысячами можно). Или выражение, значение которого нужно разложить: 2^32 + 1, 10!, 2·3·5·7 + 1. Со словом «делители» (делители 360) решатель выпишет все делители числа и их сумму, а на вопрос простое ли 97 ответит «да» или «нет» и объяснит почему.

Как раскладывать: деление по порядку

Простое число — натуральное число больше единицы, которое делится только на $1$ и на себя: $2, 3, 5, 7, 11, 13, \ldots$ Остальные числа больше единицы составные, их можно записать произведением меньших. Раскладывать число на простые множители будем так же, как это делают в тетради «лесенкой».

Пробуем делить на простые числа по возрастанию: $2, 3, 5, 7, 11, \ldots$
Пока число делится на текущее простое, делим и записываем это простое в правый столбец.
Когда перестаёт делиться, переходим к следующему простому.
Останавливаемся, когда в остатке получилась единица. Или раньше: когда очередное простое в квадрате уже больше того, что осталось, — тогда остаток сам простой.

Делители, найденные таким способом, всегда простые: на все меньшие простые число уже разделили «до упора», и составной делитель просто не успеет появиться. Проверять, делится ли число на $4$, $6$ или $9$, незачем. Ускоряют работу признаки делимости: на $2$ — последняя цифра чётная, на $3$ — сумма цифр делится на $3$, на $5$ — число оканчивается на $0$ или $5$, на $11$ — разность сумм цифр через одну делится на $11$.

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

Почему разложение единственное

Как бы вы ни раскладывали число — начиная с двойки, с пятёрки или разбив его сначала на два «удобных» множителя, как в дереве на картинке решателя, — в конце получатся одни и те же простые множители. Это не наблюдение, а теорема.

Различные простые числа, обычно их пишут по возрастанию: $p_1 < p_2 < \ldots < p_k$.

Натуральные показатели: сколько раз простое входит в разложение.

Каждое натуральное $n > 1$ так записывается, и притом единственным образом (с точностью до порядка множителей). Пример: $360 = 2^3 \cdot 3^2 \cdot 5$. Разложить $360$ как $18 \cdot 20$, как $4 \cdot 90$ или как $2 \cdot 180$ можно по-разному, но простые множители всегда будут три двойки, две тройки и одна пятёрка.

Существование доказать легко: раскладываем, пока можно, и числа всё время уменьшаются. Единственность сложнее и держится на свойстве простых чисел: если простое $p$ делит произведение $ab$, то оно делит $a$ или $b$. Отсюда же ответ на вопрос, почему единицу не считают простым числом: иначе разложения перестали бы быть единственными ($6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3\ldots$). Доказательство и история — в главе о простых числах.

Сколько у числа делителей

Из разложения сразу видны все делители. Любой делитель $360 = 2^3 \cdot 3^2 \cdot 5$ составлен из тех же простых в степенях не выше: двойка в степени от $0$ до $3$, тройка от $0$ до $2$, пятёрка от $0$ до $1$. Степени выбираются независимо друг от друга.

Показатели из разложения $n = p_1^{a_1} \cdots p_k^{a_k}$. Единица прибавляется потому, что степень может быть и нулевой: простое можно вообще не брать.

Пример: $\tau(360) = (3 + 1)(2 + 1)(1 + 1) = 24$. Сумму делителей считают похожим способом: $(1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 \cdot 13 \cdot 6 = 1170$ — если раскрыть скобки, каждый делитель появится ровно один раз.

У простого числа делителей ровно два, у квадрата простого — три ($1$, $p$, $p^2$). Нечётное число делителей бывает только у точных квадратов: делители разбиваются на пары $d$ и $n/d$, и без пары остаётся лишь $\sqrt{n}$.

Разобранные примеры

Пример 1. 360

Делим на $2$, пока делится: $360 \to 180 \to 90 \to 45$, три раза. $45$ нечётное, переходим к $3$: сумма цифр $4 + 5 = 9$ делится на $3$, и $45 \to 15 \to 5$, два раза. На $3$ пятёрка уже не делится, а на $5$ делится: $5 \to 1$.

$$\begin{array}{r|l} 360 & 2 \\ 180 & 2 \\ 90 & 2 \\ 45 & 3 \\ 15 & 3 \\ 5 & 5 \\ 1 & \end{array} \qquad 360 = 2^3 \cdot 3^2 \cdot 5.$$

Пример 2. 1001

На $2$ не делится (нечётное), на $3$ — нет (сумма цифр $2$), на $5$ — нет. На $7$ делится: $1001 = 7 \cdot 143$. Число $143$ на $7$ уже не делится ($7 \cdot 20 = 140$, остаток $3$), а на $11$ делится: $143 = 11 \cdot 13$. И $13$ простое.

$$1001 = 7 \cdot 11 \cdot 13.$$

Поэтому фокус «напишите трёхзначное число два раза подряд, и получится число, кратное $7$, $11$ и $13$» всегда работает: $\overline{abcabc} = \overline{abc} \cdot 1001$.

Пример 3. Простое ли 97?

$\sqrt{97} \approx 9{,}8$, значит, достаточно проверить простые $2, 3, 5, 7$. $97$ нечётное; сумма цифр $16$ на $3$ не делится; оканчивается не на $0$ и не на $5$; $97 = 7 \cdot 13 + 6$. Ни одно не подошло — $97$ простое. Проверять $11$ и дальше уже не нужно: $11^2 = 121 > 97$.

Пример 4. $2^{32} + 1$

Пьер Ферма заметил, что числа $2^{1} + 1 = 3$, $2^{2} + 1 = 5$, $2^{4} + 1 = 17$, $2^{8} + 1 = 257$ и $2^{16} + 1 = 65\,537$ простые, и предположил, что так будет всегда. В 1732 году Эйлер разложил следующее: $2^{32} + 1 = 4\,294\,967\,297 = 641 \cdot 6\,700\,417$. Решатель находит этот множитель пробным делением: $641$ — сто шестнадцатое по счёту простое число.

А если число большое

Пробное деление хорошо для чисел, у которых все множители небольшие. Если после деления на простые до десяти тысяч остаётся большой кусок, решатель сначала проверяет, не простой ли он (тест Миллера — Рабина), а если нет — ищет делитель ρ-методом Полларда: он находит множитель $p$ примерно за $\sqrt{p}$ шагов вместо $p$. Так за доли секунды раскладываются числа вроде $600\,851\,475\,143 = 71 \cdot 839 \cdot 1471 \cdot 6857$ и даже произведения двух тринадцатизначных простых.

Но число из двух простых множителей по сотне цифр каждый не разложит ни этот решатель, ни самый мощный компьютер за разумное время. На этом держится шифр RSA, которым защищены банковские соединения: перемножить два простых легко, а разложить произведение обратно практически невозможно. Рекорд публичного разложения такого числа — RSA-250, $829$ бит, разложено в 2020 году; вычисления заняли около 2700 лет работы одного процессорного ядра. Как устроен шифр — в главе об арифметике остатков.

Типичные ошибки

Оставляют составной множитель. $360 = 4 \cdot 9 \cdot 10$ — разложение, но не на простые: $4$, $9$ и $10$ нужно разложить дальше.
Теряют повторяющиеся множители. $360 = 2 \cdot 3 \cdot 5$ — неверно: это $30$. Двойка входит трижды, тройка дважды; делить нужно, пока делится.
Пишут единицу множителем. $1$ не простое число, в разложение её не включают.
Принимают составное число за простое. Классические ловушки: $51 = 3 \cdot 17$, $57 = 3 \cdot 19$, $91 = 7 \cdot 13$, $221 = 13 \cdot 17$. Выглядят «простыми», но у каждого есть делитель меньше корня.
Бросают проверку раньше корня. Чтобы доказать, что $221$ простое, мало проверить $2, 3, 5, 7, 11$: $\sqrt{221} \approx 14{,}9$, и на $13$ оно делится.
Считают делители по показателям без единицы. У $2^3 \cdot 3^2$ не $3 \cdot 2 = 6$ делителей, а $(3 + 1)(2 + 1) = 12$.

Что ещё посмотреть

Решето Эратосфена, бесконечность простых чисел и открытые вопросы о них — в главе «Простые числа». Из разложений двух чисел получаются их НОД и НОК, но быстрее их даёт алгоритм Евклида: смотрите решатель НОД и НОК и главу о делимости. Разложение знаменателя подсказывает, будет ли десятичная дробь конечной, — это видно в калькуляторе дробей.