Priemfactorisatie rekenmachine
Schrijf een getal als product van priemgetallen en zie meteen of het zelf priem is.
Priemfactorisatie
Priemfactorisatie: 2³ × 3² × 5
- Uitgeschreven
- 2 × 2 × 2 × 3 × 3 × 5
- Aantal delers
- 24
- Volgend priemgetal
- 367
- Vorig priemgetal
- 359
Dit getal is samengesteld: het heeft delers naast 1 en het getal zelf.
| Priemgetal | Macht | Waarde |
|---|---|---|
| 2 | 3 | 8 |
| 3 | 2 | 9 |
| 5 | 1 | 5 |
Hoe het werkt
Elk geheel getal boven 1 is op precies één manier een product van priemgetallen, op de volgorde na. De rekenmachine deelt eerst door kleine priemgetallen en gebruikt daarna de rho-methode van Pollard om grotere factoren te splitsen.
Elke factor wordt bevestigd als priem met de deterministische Miller–Rabin-test, die voor getallen van deze grootte bewezen juist is. Het aantal delers volgt uit de exponenten: tel bij elk 1 op en vermenigvuldig.
Formule
n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ delers = (a₁ + 1)(a₂ + 1)…(aₖ + 1)
Uitgewerkt voorbeeld
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. Het heeft (3 + 1)(2 + 1)(1 + 1) = 24 delers. De dichtstbijzijnde priemgetallen zijn 359 en 367.
Veelgestelde vragen
Is 1 een priemgetal?
Nee. Een priemgetal heeft precies twee delers, 1 en zichzelf; 1 heeft er maar één. Door 1 uit te sluiten blijft de priemfactorisatie uniek.
Is 2 het enige even priemgetal?
Ja. Elk ander even getal is deelbaar door 2, dus het heeft minstens drie delers.
Hoe weet men of een groot getal priem is?
Proefdelen is voor grote getallen te traag, dus worden tests zoals Miller–Rabin gebruikt. Met de juiste testbasen geeft die voor getallen van deze grootte een zeker antwoord.