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

Розкладання числа на прості множники

Кожне ціле число, більше за 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, після чого рекурсивно продовжує розкладання. Завдяки цьому навіть добутки двох простих чисел порядку десятків мільйонів обробляються швидко, тоді як звичайне пробне ділення було б повільним. Дерево множників показує один зі способів дійти до простих чисел, відокремлюючи на кожному кроці найменший простий множник.

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