Primfaktortre

Primtallsfaktorisering bryter et heltall ned til primtallene som multipliseres for å danne det – den ene oppdelingen ethvert sammensatt tall har, og nøyaktig én. Dette verktøyet tar ethvert heltall på 2 eller mer og faktoriserer det på ordentlig, og tegner deretter resultatet som forgreiningsfaktortreet fra skolen: start med tallet, trekk ut den minste primfaktoren, og fortsett å splitte resten til bare primtall er igjen.

Splitteregelen er prøvedivisjon med den minste mulige primfaktoren i hvert steg: prøv 2 først, deretter oddetallene 3, 5, 7, 9 … opp til kvadratroten av den gjeldende verdien. For 360 utspiller det seg som 360 = 2 × 180, så 180 = 2 × 90, så 90 = 2 × 45, så 45 = 5 × 9, og til slutt 9 = 3 × 3 – fem splittinger som ender i seks primtallsblader (2, 2, 2, 3, 3, 5). Opptellingen av disse bladene gir den kompakte potensformen som vises under diagrammet: 360 = 2³ × 3² × 5.

Alt dette kjøres med nøyaktig BigInt-aritmetikk, så det oppstår aldri noe flyttallsavrunding underveis. Prøvedivisjon opp til kvadratroten er raskt for vanlige tall, men blir tregere jo større den minste primfaktoren i tallet er; verktøyet begrenser derfor inndata til 1 000 000 000 000 (10^12) og gir en ærlig melding utover det i stedet for å fryse fanen – en nettleser har ingenting med å henge seg opp i et kjempestort semiprimtall bare for å bevise et poeng.

Et visuelt faktortre er standardmåten primtallsfaktorisering læres på i skolen, og det forblir nyttig lenge etter klasserommet: å forkorte brøker, finne største felles faktor eller minste felles multiplum ved å sammenligne primtallspotenser, forenkle kvadratrøtter og stikkprøve om et tall er primtall – alt kommer tilbake til den samme faktoriseringen. Alt kjøres lokalt i nettleseren din – ingen registrering, ingen tur til serveren.