Primært faktoriseringstræ

Primfaktorisering opdeler et helt tal i de primtal, der ganges sammen for at gøre det - den ene nedbrydning, som hvert sammensat tal har, og præcis et. Dette værktøj tager ethvert heltal på 2 eller mere og faktoriserer det for rigtigt, og tegner derefter resultatet som det forgreningsfaktortræ, der blev undervist i skolen: start med tallet, del dets mindste primtal af, og fortsæt med at dele det resterende stykke, indtil der kun er primtal tilbage.

Opdelingsreglen er prøvedivision med det mindst mulige primtal ved hvert trin: prøv først 2, derefter ulige tal 3, 5, 7, 9... op til kvadratroden af ​​den aktuelle værdi. For 360 udspiller det sig som 360 = 2 × 180, derefter 180 = 2 × 90, derefter 90 = 2 × 45, derefter 45 = 5 × 9, derefter 9 = 3 × 3 — fem opdelinger, der ender med seks prime blade (2, 2, 2, 3, 3, 5). Optælling af disse blade giver den kompakte eksponentform vist under diagrammet: 360 = 2³ × 3² × 5.

Alt dette kører med nøjagtig BigInt-aritmetik, så der er aldrig nogen flydende komma-afrunding på vej ned. Prøvedeling op til kvadratroden er hurtig for daglige tal, men bliver langsommere, jo større inputets mindste primfaktor er, så værktøjet begrænser input til 1.000.000.000.000 (10^12) og rapporterer en ærlig besked ud over det i stedet for at fryse fanen - en browser har ingen forretning at hænge på et kæmpe semi-prime-punkt.

Et visuelt faktortræ er standardmåden, hvorpå primtalsfaktorisering undervises i skolen, og det forbliver nyttigt langt ud over klasseværelset: at reducere brøker, finde den største fælles faktor eller mindste fælles multiplum ved at sammenligne primpotenser, forenkle kvadratrødder og stikprøve af, om et tal er primtal, kommer alle tilbage til den samme dekomponering. Alt kører lokalt i din browser - ingen tilmelding, ingen server rundtur.