Primtalsfaktortræ

Primtalsfaktorisering nedbryder et helt tal til de primtal, der multipliceres for at danne det — den eneste dekomponering, ethvert sammensat tal har, og kun én. Dette værktøj tager ethvert heltal på 2 eller derover, faktoriserer det reelt og tegner derefter resultatet som det forgrenede faktortræ, der læres i skolen: Start med tallet, split den mindste primfaktor fra, og bliv ved med at splitte resten, indtil der kun er primtal tilbage.

Splittereglen er prøvedivision med den mindst mulige primfaktor i hvert trin: prøv 2 først, derefter de ulige tal 3, 5, 7, 9... op til kvadratroden af den aktuelle værdi. For 360 forløber det sådan: 360 = 2 × 180, dernæst 180 = 2 × 90, så 90 = 2 × 45, så 45 = 5 × 9, og så 9 = 3 × 3 — fem splits, der ender med seks primtalsblade (2, 2, 2, 3, 3, 5). Optælling af disse blade giver den kompakte potensform vist under diagrammet: 360 = 2³ × 3² × 5.

Alt dette kører med eksakt BigInt-aritmetik, så der er ingen afrundingsfejl fra floating-point undervejs. Prøvedivision op til kvadratroden er hurtig til dagligdags tal, men bliver langsommere, jo større det indtastede tals mindste primfaktor er, så værktøjet sætter en øvre grænse på 1.000.000.000.000 (10^12) og viser en ærlig besked, hvis tallet er større, i stedet for at fryse fanen — en browser bør ikke hænge på et kæmpestort semiprimtal bare for at bevise en pointe.

Et visuelt faktortræ er den standardmetode, primtalsfaktorisering læres på i skolen, og den er nyttig langt ud over klasseværelset: at forkorte brøker, finde den største fælles divisor eller det mindste fælles multiplum ved at sammenligne primtalspotenser, forenkle kvadratrødder og tjekke, om et tal er et primtal, handler alt sammen om den samme dekomponering. Alt kører lokalt i din browser — ingen tilmelding, ingen kommunikation med server.