Ontbinding in priemfactoren
Ontbind een geheel getal in zijn priemfactoren, toon zijn delers en controleer of het een priemgetal is.
Draait volledig in je browser. Er wordt niets geüpload, gelogd of opgeslagen.
Priemfactorontbinding
2^3 × 3^2 × 5
- Priemgetal?
- nee
- Verschillende priemfactoren
- 3
- Aantal delers
- 24
- Delers
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Elk geheel getal groter dan 1 is een product van priemgetallen, en er bestaat maar één zo'n product voor: dat is de hoofdstelling van de rekenkunde. Deze tool vindt dat product, en daarmee alles wat eruit volgt: hoeveel delers het getal heeft en welke dat zijn.
Hoe het werkt
Proefdeling, met een kortere weg: zodra 2 en 3 eruit zijn gehaald, ligt elk overgebleven priemgetal direct naast een veelvoud van zes, dus de kandidaten gaan met stappen van zes vooruit in plaats van twee. Wat de zeef overleeft is priem en komt erbij als laatste factor.
De delers worden opgebouwd uit de ontbinding en niet door elk getal tot n te proberen. Een getal geschreven als 2³ × 3² × 5 heeft (3+1) × (2+1) × (1+1) = 24 delers, en elke deler is een keuze van hoeveel van elk priemgetal je neemt, dus ze opsommen kost niets zodra de ontbinding bekend is.
De grens is een biljoen. Proefdeling gaat hooguit tot de vierkantswortel van het getal, en dat is daar een miljoen stappen: snel. Daarboven zou een getal dat het product van twee grote priemgetallen blijkt te zijn de pagina een minuut laten laden, dus wordt het geweigerd.
Voorbeelden
| Geval | Invoer | Resultaat |
|---|---|---|
| Een getal met veel delers | 360 | 2³ × 3² × 5: 24 delers |
| Een priemgetal | 97 | 97: priem, 2 delers |
| Een macht van twee | 1024 | 2¹⁰: 11 delers |
Veelgestelde vragen
Waarom begint het bij 2 en niet bij 1?
Omdat 1 geen priemfactorontbinding heeft, en het priem noemen de eenduidigheid zou breken waarop het hele onderwerp steunt: als 1 priem was, zou 6 gelijk zijn aan 2 × 3, en 1 × 2 × 3, en 1 × 1 × 2 × 3, en zou er geen enkel antwoord meer zijn. Nul is nog erger: elk getal is er een deler van.
Hoeveel delers heeft een getal?
Tel één op bij elke exponent in de ontbinding en vermenigvuldig. 360 is 2³ × 3² × 5, dus 4 × 3 × 2 = 24. Een priemgetal heeft er 2 – zichzelf en 1 – en een kwadraat heeft er altijd een oneven aantal, omdat een van de delers zijn eigen partner is.
Waarom is er een grens?
Proefdeling is exact en snel tot ze dat niet meer is. Het slechtste geval is een product van twee priemgetallen dicht bij de vierkantswortel, en de grens hier ligt waar dat geval nog binnen één keer laden van de pagina een antwoord geeft. Een weigering vertelt je wat er is gebeurd; een time-out vertelt je niets.
Worden encryptiesleutels zo gekraakt?
Nee, en daar draait het juist om. RSA steunt op hoe moeilijk het is een getal van een paar honderd cijfers te ontbinden; proefdeling op zo'n getal zou langer duren dan het heelal bestaat. Er bestaan betere methoden, en ook die komen er niet in de buurt, en daarom werkt het systeem.
Goed om te weten
- Delers worden volledig opgesomd tot vierenzestig; daarboven wordt alleen het aantal getoond, want een pagina met negenhonderd getallen leest niemand.