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

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

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