Rozkladový strom na prvočinitele

Rozklad na prvočinitele rozdělí celé číslo na prvočísla, jejichž součinem je původní číslo – je to rozklad, který má každé složené číslo právě jeden. Tento nástroj vezme libovolné celé číslo větší nebo rovné 2 a skutečně ho rozloží, a poté výsledek nakreslí jako rozkladový strom, který znáte ze školy: začněte zadaným číslem, odtrhněte jeho nejmenší prvočinitel a zbytek dělte dál, dokud nezůstanou jen prvočísla.

Pravidlo dělení je v každém kroku zkoušení dělitelnosti nejmenším možným prvočíslem: nejprve 2, poté lichá čísla 3, 5, 7, 9… až k odmocnině aktuální hodnoty. Pro 360 to vypadá takto: 360 = 2 × 180, poté 180 = 2 × 90, poté 90 = 2 × 45, poté 45 = 5 × 9, poté 9 = 3 × 3 – pět rozkladů končících šesti prvočíselnými listy (2, 2, 2, 3, 3, 5). Sečtením těchto listů získáme kompaktní tvar s exponenty, který se ukazuje pod diagramem: 360 = 2³ × 3² × 5.

To vše běží s přesnou aritmetikou BigInt, takže během cesty dolů nedochází k žádnému zaokrouhlování v plovoucí řádové čárce. Zkoušení dělitelů až do odmocniny je pro běžná čísla rychlé, ale zpomaluje se s rostoucí velikostí nejmenšího prvočinitele vstupu; proto nástroj omezuje vstup na 1 000 000 000 000 (10^12) a nad tuto hodnotu zobrazí poctivou hlášku, místo aby zasekl záložku – prohlížeč nemá co ztrácet čas obřím poloprvočíslem jen proto, aby ukázal, že na to má.

Vizuální rozkladový strom je standardní způsob, jak se na školách vyučuje rozklad na prvočinitele, a svou užitečnost si drží i dlouho po škole: zjednodušování zlomků, hledání největšího společného dělitele nebo nejmenšího společného násobku porovnáním mocnin prvočísel, odmocňování i ověření, zda je číslo prvočíslem – to vše se opírá o tentýž rozklad. Vše běží lokálně ve vašem prohlížeči – bez registrace, bez posílání dat na server.