Что такое разложение на простые множители?
Разложение на простые множители (его также называют факторизацией целого числа или каноническим разложением) — это представление натурального числа в виде произведения простых чисел. Согласно основной теореме арифметики, у любого целого числа больше 1 такое разложение единственно с точностью до порядка множителей. Этот калькулятор находит простые множители для любого целого числа от 2 до почти 10 триллионов (13 знаков) и показывает результат в четырёх видах: как произведение, в степенной форме, в виде списка CSV и при желании — в виде дерева множителей.
Как пользоваться
Введите в поле натуральное число больше 1 и нажмите кнопку. Поставьте галочку «Построить дерево разложения», если хотите увидеть наглядную схему. В результате вы получите выписанные простые множители (например, 2 x 2 x 5 x 5), компактную степенную форму (2^2 x 5^2), список через запятую, количество различных простых множителей, общее число простых множителей с учётом кратности, а также индекс Prime[n] для каждого множителя из первых 5000 простых чисел.
Формула и алгоритм
Калькулятор использует метод пробного деления. Сначала он убирает все множители 2, затем проверяет нечётные делители 3, 5, 7, ... до тех пор, пока квадрат делителя не превысит оставшееся значение. Каждый раз, когда делитель делит число нацело, он записывается и выносится. Всё, что остаётся больше 1 в конце, само является простым множителем. Проверять делители достаточно до квадратного корня, потому что у любого составного числа обязательно есть делитель, не превосходящий его квадратного корня.
$$\text{Number} = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$$
Разбор примера: n = 100
\(100 / 2 = 50\), \(50 / 2 = 25\) — значит, две двойки. Дальше 25 не делится на 3, но делится на 5: \(25 / 5 = 5\), \(5 / 5 = 1\), то есть две пятёрки. Множители: 2, 2, 5, 5. В виде произведения это 2 x 2 x 5 x 5, в степенной форме — 2^2 x 5^2. Здесь 2 различных простых числа и 4 множителя всего. Проверка: $$2 \times 2 \times 5 \times 5 = 100$$ Индексы простых чисел: \(2 = \text{Prime}[1]\), \(5 = \text{Prime}[3]\).
Частые вопросы
А как насчёт числа 1? Число 1 не является ни простым, ни составным и не имеет простых множителей, поэтому калькулятор отдельно сообщает об этом особом случае.
Что, если моё число простое? У простого числа, например 13, единственный простой множитель — оно само; степенная форма в этом случае — просто 13.
Какое максимальное число можно разложить? Почти до 10 триллионов. Числа, близкие к этому пределу и имеющие большой простой множитель, могут считаться чуть дольше, ведь пробное деление перебирает делители вплоть до квадратного корня.
