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

Простых множителей с повторами	6
Различных простых множителей	3

Как число превращается в произведение простых множителей

Составное число разделено на повторяющиеся группы геометрических фишек под лупой

Разложение на простые множители представляет целое число как произведение простых чисел. Простое число больше 1 делится без остатка только на 1 и на себя. Например, 360 = 2³ × 3² × 5. Запись со степенями называют канонической: она коротко показывает сами множители и число их повторов.

Для любого положительного целого n > 1 такая запись существует и единственна, если не считать перестановку множителей. Это основная теорема арифметики. В справочнике NIST DLMF, раздел 27.2 каноническая форма записана как произведение различных простых p в положительных целых степенях a.

\displaystyle n=\varepsilon\prod_{i=1}^{k}p_i^{a_i},\qquad \varepsilon\in\{-1,1\}

Знак ε нужен для отрицательных чисел. Множитель −1 показывает знак, но сам не является простым. Поэтому в счётчики простых множителей он не входит. У 1 и −1 простых множителей нет.

Почему достаточно пробного деления

Калькулятор сначала делит модуль n на 2, пока деление остаётся целым. Затем проверяет 3, 5, 7 и остальные нечётные кандидаты. Чётные после 2 пропускаются: они точно не простые. Каждое успешное деление уменьшает остаток, поэтому верхняя граница поиска сокращается прямо во время расчёта.

Перебор останавливается, когда кандидат d становится больше текущего остатка, делённого на d. Это то же условие, что d² больше остатка, но без дробного корня. Если после этого осталось число больше 1, оно само простое. При предельном вводе 10¹² начальный квадратный корень равен 10⁶, значит, кандидаты выше миллиона не понадобятся.

В раскрываемом блоке каждый успешный шаг показан как обычное деление. По нему легко проверить степени: три деления на 2 дают 2³. Главный ответ сжимает повторы в степень, а два счётчика показывают количество множителей с повторами и без них.

Примеры, которые проверяют разные случаи

🧩 Составное число 360. Последовательные деления дают 360 = 2³ × 3² × 5. Всего простых множителей шесть, а различных три. Запись сразу показывает, что число делится на 8, 9 и 5.

➖ Отрицательное число −84. Модуль 84 равен 2² × 3 × 7, поэтому полная запись выглядит так: −84 = −1 × 2² × 3 × 7. Минус не теряется и не искажает состав простых множителей.

▫️ Единица 1. Калькулятор сообщит, что простых множителей нет. Это не ошибка: единица служит нейтральным множителем и не входит в список простых чисел. Поэтому число множителей с повторами и без них равно 0.

💎 Простое число 999 983. Ни один кандидат до квадратного корня не делит его без остатка. Разложение состоит из одного множителя 999 983. Для отдельного вердикта можно открыть проверку числа на простоту.

🏗 Триллион 10¹². Поскольку 10 = 2 × 5, двенадцать нулей дают 10¹² = 2¹² × 5¹². Простых множителей с повторами 24, а различных всего 2. Этот пример одновременно проверяет верхнюю границу ввода и двузначную степень.

🔗 Произведение 2 310. Разложение 2 310 = 2 × 3 × 5 × 7 × 11 содержит пять различных простых и ни одного повтора. Такая запись полезна для теста алгоритма: он должен пройти пять разных делителей и не склеить их в степени.

Что можно вывести из канонической записи

Степени сразу дают количество положительных делителей. Для каждого простого множителя делитель выбирает показатель от 0 до соответствующей степени в разложении. Поэтому для 360 = 2³ × 3² × 5 получаем (3 + 1) × (2 + 1) × (1 + 1) = 24 делителя. Готовый список и их сумму показывает калькулятор делителей.

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

Для некоторых арифметических функций важен только набор различных простых. Например, функция Эйлера φ(n) для 36 = 2² × 3² использует двойку и тройку по одному разу. Показатели степени нужны для исходного числа, но не повторяют множитель формулы.

Границы ввода и точность

Калькулятор принимает ненулевые целые числа от −1 000 000 000 000 до 1 000 000 000 000. Дробная часть отклоняется, потому что каноническое разложение здесь определено для целых. Пробелы между разрядами не меняют число. Расчёт идёт в целочисленной арифметике, поэтому округления нет.

Ноль является особым случаем. Его делит любое ненулевое целое, поэтому конечную каноническую цепочку для него составить нельзя. Ошибка на нуле защищает от ложного ответа вроде «множителей нет», который верен для 1, но не для 0.

Скорость зависит не только от размера n, но и от его структуры. Чётное число быстро теряет множители 2, а большое простое требует проверки всех нечётных кандидатов до корня. Верхняя граница в 1 трлн делает этот худший сценарий предсказуемым.

Вопросы о разложении на простые множители

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

Что такое каноническое разложение?

Это произведение различных простых множителей, записанных в положительных целых степенях. Порядок множителей обычно выбирают по возрастанию.

Почему единица не считается простым числом?

Простое число должно иметь ровно два положительных делителя. У 1 только один делитель, поэтому она не простая и не составная.

Зачем в разложении отрицательного числа нужен множитель −1?

Простые множители раскладывают модуль числа. Множитель −1 возвращает отрицательный знак, но не входит в количество простых множителей.

Почему ноль нельзя разложить так же?

Любое ненулевое целое делит 0. Поэтому у нуля нет единственного конечного набора простых множителей.

Чем отличаются множители с повторами и различные множители?

В записи 360 = 2³ × 3² × 5 повторы дают 3 + 2 + 1 = 6 множителей. Различных простых всего три: 2, 3 и 5.

Как быстро проверить готовое разложение?

Возведите каждый простой множитель в указанную степень и перемножьте результаты. Для отрицательного n в конце учтите множитель −1.

Почему алгоритм перестаёт проверять делители после квадратного корня?

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

Можно ли получить другое разложение того же числа?

Набор простых и их степени единственны. Можно переставить множители, например 2 × 3 и 3 × 2, но сам состав от этого не меняется.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.