Priemfactorisatie-calculator

Een getal ontbinden in priemfactoren

Elk geheel getal groter dan 1 kan op precies één manier worden geschreven als product van priemgetallen, afgezien van de volgorde van de factoren. Dit is de hoofdstelling van de rekenkunde, en de priemfactorisatie van een getal is dat unieke product. Bijvoorbeeld 360 = 2³ × 3² × 5. Deze calculator bepaalt de ontbinding van elk geheel getal tot 9,007,199,254,740,991, oftewel 2^53 − 1, het grootste gehele getal dat een browser exact kan weergeven. Resultaten verschijnen in exponentvorm, in volledig uitgeschreven vorm en als factorboom.

Delers, hun aantal en hun som

Zodra je de priemfactorisatie kent, volgen veel andere eigenschappen direct. Als een getal gelijk is aan p₁^a₁ × p₂^a₂ × …, dan is het aantal positieve delers (a₁ + 1)(a₂ + 1)…, omdat elke deler voor elk priemgetal een exponent kiest van 0 tot en met de volledige macht. De som van de delers is het product van (1 + p + p² + … + p^a) over de priemgetallen. Voor 360 levert dat 4 × 3 × 2 = 24 delers op met een som van 1170. De tool toont alle delers in oplopende volgorde, wat helpt bij taken zoals gemeenschappelijke factoren vinden, breuken vereenvoudigen en controleren of een getal volmaakt is, wat betekent dat de delers behalve het getal zelf samen precies dat getal opleveren.

Hoe het ontbinden werkt

Kleine priemfactoren worden verwijderd door proefdeling met een wiel dat veelvouden van 2 en 3 overslaat. Wat overblijft heeft alleen grote priemfactoren, dus de calculator controleert het met een deterministische Miller-Rabin-test, en als het samengesteld is, wordt het gesplitst met het algoritme Pollard's rho met exacte BigInt-rekenkunde en daarna recursief ontbonden. Daardoor geven zelfs producten van twee priemgetallen in de tientallen miljoenen snel een resultaat, terwijl zuivere proefdeling traag zou zijn. De factorboom toont één manier om de priemgetallen te bereiken door bij elke stap het kleinste priemgetal af te splitsen.

In de batchmodus plak je een hele lijst getallen en krijg je een tabel met elke ontbinding en het aantal delers, terwijl ongeldige invoer afzonderlijk wordt gemarkeerd in plaats van de hele verwerking te stoppen. Alles wordt in je browser berekend, dus de getallen die je invoert worden nooit geüpload.