Drevo prafaktorjev

Razcep na prafaktorje razbije celo število na praštevila, ki med seboj pomnožena tvorijo to število – to je ena sama razčlenitev, ki jo ima vsako sestavljeno število, in sicer natanko ena. To orodje vzame poljubno celo število 2 ali več in ga zares faktorizira, nato pa rezultat izriše kot razvejano drevo faktorjev, kot ga učijo v šoli: začnite s številom, odcepite njegov najmanjši prafaktor in nadaljujte z razcepljanjem preostanka, dokler ne ostanejo samo praštevila.

Pravilo razcepa je poskusno deljenje z najmanjšim možnim praštevilom na vsakem koraku: najprej poskusite z 2, nato z lihimi števili 3, 5, 7, 9… do kvadratnega korena trenutne vrednosti. Za 360 to pomeni 360 = 2 × 180, nato 180 = 2 × 90, nato 90 = 2 × 45, nato 45 = 5 × 9, nato 9 = 3 × 3 – pet razcepov, ki se končajo s šestimi praštevilskimi listi (2, 2, 2, 3, 3, 5). Preštevanje teh listov da kompaktno obliko s potencami, prikazano pod diagramom: 360 = 2³ × 3² × 5.

Vse to deluje z natančno aritmetiko BigInt, zato na poti navzdol nikoli ne pride do zaokroževanja s plavajočo vejico. Poskusno deljenje do kvadratnega korena je hitro za običajna števila, vendar postaja počasnejše, čim večji je najmanjši prafaktor vnosa, zato orodje omeji vnos na 1.000.000.000.000 (10^12) in nad to mejo prikaže iskreno sporočilo, namesto da bi zamrznilo zavihek – brskalnik se nima kaj obešati na ogromnem polpraštevilu samo zato, da bi nekaj dokazoval.

Vizualno drevo faktorjev je standardni način, kako v šoli poučujejo razcep na prafaktorje, in ostane uporabno tudi daleč onkraj učilnice: krajšanje ulomkov, iskanje največjega skupnega delitelja ali najmanjšega skupnega večkratnika s primerjavo praštevilskih potenc, poenostavljanje kvadratnih korenov in preverjanje, ali je število praštevilo, vse temelji na isti razčlenitvi. Vse deluje lokalno v vašem brskalniku – brez prijave, brez pošiljanja na strežnik.