Дерево розкладу на прості множники

Розклад на прості множники розбиває ціле число на прості числа, які множаться, щоб утворити його, — єдиний розклад, який має кожне складене число, і лише один. Цей інструмент бере будь-яке ціле число від 2 і більше, справді факторизує його, а потім малює результат у вигляді гіллястого дерева множників, яке вивчають у школі: почніть із числа, відділіть від нього найменший простий множник і продовжуйте ділити залишок, поки не залишаться лише прості числа.

Правило розбиття — пробне ділення на найменший можливий простий множник на кожному кроці: спершу пробуємо 2, потім непарні числа 3, 5, 7, 9... до квадратного кореня поточного значення. Для 360 це виглядає так: 360 = 2 × 180, потім 180 = 2 × 90, потім 90 = 2 × 45, потім 45 = 5 × 9, потім 9 = 3 × 3 — п'ять розщеплень, що закінчуються шістьма простими листочками (2, 2, 2, 3, 3, 5). Підрахунок цих листочків дає компактний степеневий запис, показаний під діаграмою: 360 = 2³ × 3² × 5.

Усе це працює з точною арифметикою BigInt, тому під час спуску ніколи не виникає заокруглень із плаваючою комою. Пробне ділення до квадратного кореня є швидким для повсякденних чисел, але сповільнюється зі зростанням найменшого простого множника вхідного числа, тому інструмент обмежує вхід числом 1 000 000 000 000 (10^12) і видає чесне повідомлення для більших чисел, замість того щоб зависнути вкладці — браузер не повинен застрягати на гігантському напівпростому числі лише заради демонстрації.

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