Калькулятор разложения на простые множители

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

Любое целое число больше 1 можно записать в виде произведения простых чисел единственным образом, с точностью до порядка множителей. Это основная теорема арифметики, а разложение числа на простые множители и есть это единственное произведение. Например, 360 = 2³ × 3² × 5. Этот калькулятор находит разложение любого натурального числа до 9,007,199,254,740,991, то есть 2^53 − 1 — наибольшего целого числа, которое браузер может представить точно. Результаты выводятся в виде записи со степенями, в полностью развёрнутом виде и в виде дерева множителей.

Делители, их количество и сумма

Зная разложение на простые множители, можно сразу получить многие другие свойства. Если число равно p₁^a₁ × p₂^a₂ × …, то количество его натуральных делителей равно (a₁ + 1)(a₂ + 1)…, поскольку каждый делитель выбирает для каждого простого множителя показатель от 0 до полной степени. Сумма делителей равна произведению (1 + p + p² + … + p^a) по всем простым множителям. Для 360 это даёт 4 × 3 × 2 = 24 делителя с суммой 1170. Инструмент выводит все делители в порядке возрастания, что помогает находить общие множители, сокращать дроби и проверять, является ли число совершенным, то есть равна ли сумма его делителей, кроме самого числа, этому числу.

Как работает разложение

Малые простые множители отделяются методом пробного деления с использованием колеса, пропускающего числа, кратные 2 и 3. У оставшейся части есть только большие простые множители, поэтому калькулятор проверяет её детерминированным тестом Miller-Rabin, а если она составная, разбивает её алгоритмом Pollard's rho с точной арифметикой BigInt и затем рекурсивно раскладывает дальше. Благодаря этому даже произведения двух простых чисел порядка десятков миллионов раскладываются быстро, тогда как чистое пробное деление работало бы медленно. Дерево множителей показывает один из способов прийти к простым числам, отделяя на каждом шаге наименьший простой множитель.

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