Priemgetal controleren

Zo controleer je of een getal priem is

1. Typ een Geheel getal. Expressies mogen ook: 2^61-1, 10^12+39, 20!+1 of 3711.
2. Het antwoord verschijnt terwijl je typt; klik op Controleren om de ontbinding van een lastig getal meer tijd te geven.
3. Lees het oordeel, de Priemfactorisatie, het Aantal delers, het Vorig priemgetal en het Volgend priemgetal. Het paneel Waarom legt uit hoe het antwoord tot stand kwam, en Ontbinding kopiëren kopieert het product van priemfactoren.
4. Wil je een lijst met priemgetallen, vul dan Van en Tot en met in onder Priemgetallen in een bereik en klik op Priemgetallen tonen.

Getallen tot 2048 bits (ongeveer 617 cijfers) worden geaccepteerd, en alles draait in je browser.

Wanneer is een getal een priemgetal?

Een priemgetal is een geheel getal groter dan 1 dat alleen deelbaar is door 1 en door zichzelf: 2, 3, 5, 7, 11, 13… Een getal met andere delers is samengesteld en kan op precies één manier geschreven worden als product van priemgetallen, de priemfactorisatie (360 = 2³ × 3² × 5). De getallen 0 en 1 zijn priem noch samengesteld, en 2 is het enige even priemgetal.

Het aantal delers volgt uit de ontbinding: tel bij elke exponent 1 op en vermenigvuldig. 360 = 2³ × 3² × 5 heeft (3 + 1)(2 + 1)(1 + 1) = 24 delers. Een priemgetal heeft er altijd precies 2.

Hoe de test werkt

• Kleine getallen (onder een miljoen) worden gecontroleerd door proefdeling: als geen enkel priemgetal tot de wortel het getal deelt, is het priem. Verder zoeken is niet nodig, want een samengesteld getal heeft altijd een factor die niet groter is dan zijn wortel.
• Grotere getallen worden eerst gedeeld door elk priemgetal onder 1000 en daarna onderworpen aan de Miller-Rabintest. Met de 13 bases 2, 3, 5, …, 41 is bewezen dat deze test exact is voor elk getal onder 3,3 × 10²⁴, dus ook voor alle 64-bitsgetallen. Voor die getallen is het antwoord zeker.
• Boven 3,3 × 10²⁴ worden 25 bases gebruikt, en een getal dat ze allemaal doorstaat, wordt gemeld als waarschijnlijk priem. De kans op een fout is kleiner dan 1 op 10¹⁵, maar het is geen wiskundig bewijs. Faalt de test, dan is het getal zeker samengesteld.

Hoe getallen ontbonden worden

Kleine factoren worden gevonden met proefdeling. Grotere samengestelde delen worden gesplitst met het rho-algoritme van Pollard (de variant van Brent), dat factoren tot ongeveer 10 cijfers in een fractie van een seconde vindt. Moeilijkere getallen, zoals het product van twee priemgetallen van 15 cijfers of meer, kunnen veel langer duren dan welke tijdslimiet ook, dus het ontbinden stopt na een paar seconden. De laatste factor wordt dan gemarkeerd als samengesteld maar niet gesplitst, en opnieuw op Controleren klikken geeft hem meer tijd.

Priemgetallen in een bereik

De lijst gebruikt een gesegmenteerde zeef van Eratosthenes, die de veelvouden van elk priemgetal wegstreept. Er passen maximaal 1.000.000 getallen in een bereik, met een bovengrens tot 10¹². De telling geldt voor het hele bereik, en de eerste 2.000 priemgetallen worden getoond. Er zijn bijvoorbeeld 25 priemgetallen tussen 1 en 100 en 78.498 onder een miljoen.