Primtalstjek

Sådan bruger du primtalstjekket

1. Skriv et Helt tal. Udtryk accepteres også: 2^61-1, 10^12+39, 20!+1 eller 3711.
2. Svaret vises, mens du skriver. Tryk på Kontrollér for at give faktoriseringen mere tid på et svært tal.
3. Aflæs dommen, Primtalsfaktorisering, Antal divisorer, Forrige primtal og Næste primtal. Panelet Hvorfor forklarer, hvordan svaret blev nået, og Kopiér faktorisering kopierer produktet af primtal.
4. For at vise primtal udfylder du Fra og Til under Primtal i et interval og trykker på Vis primtal.

Tal op til 2048 bit (omkring 617 cifre) accepteres, og alt kører i din browser. Intet, du indtaster, sendes til en server.

Hvad der gør et tal til et primtal

Et primtal er et helt tal større end 1, hvis eneste divisorer er 1 og tallet selv: 2, 3, 5, 7, 11, 13 … Et tal med andre divisorer er sammensat og kan skrives på præcis én måde som et produkt af primtal, dets primtalsfaktorisering (360 = 2³ × 3² × 5). Tallene 0 og 1 er hverken primtal eller sammensatte, og 2 er det eneste lige primtal.

Antallet af divisorer følger af faktoriseringen: Læg 1 til hver eksponent, og gang. 360 = 2³ × 3² × 5 har (3 + 1)(2 + 1)(1 + 1) = 24 divisorer. Et primtal har altid præcis 2.

Sådan virker testen

• Små tal (under en million) kontrolleres ved prøvedivision: Hvis intet primtal op til kvadratroden går op i tallet, er det et primtal. Man behøver ikke gå videre, fordi et sammensat tal altid har en faktor, der ikke er større end dets kvadratrod.
• Større tal divideres først med alle primtal under 1000 og sendes derefter gennem Miller–Rabin-testen. Med de 13 baser 2, 3, 5, …, 41 er testen bevist eksakt for alle tal under 3,3 × 10²⁴, hvilket omfatter alle 64-bit-heltal. For disse tal er svaret sikkert.
• Over 3,3 × 10²⁴ bruges 25 baser, og et tal, der består dem alle, meldes som et sandsynligt primtal. Sandsynligheden for fejl er under 1 ud af 10¹⁵, men det er ikke et matematisk bevis. Når testen fejler, er tallet helt sikkert sammensat.

Sådan faktoriseres tal

Små faktorer findes ved prøvedivision. Større sammensatte dele deles med Pollards rho-algoritme (Brents variant), som finder faktorer på op til omkring 10 cifre på en brøkdel af et sekund. Sværere tal, for eksempel produktet af to primtal på 15 cifre eller mere, kan tage langt længere tid end enhver tidsgrænse, så faktoriseringen stopper efter nogle sekunder. Den sidste faktor markeres da som sammensat, men ikke delt, og et nyt tryk på Kontrollér giver den mere tid.

Primtal i et interval

Intervallisten bruger en segmenteret Eratosthenes’ si, som streger multiplum af hvert primtal ud. Den accepterer op til 1.000.000 tal pr. interval med en øvre grænse op til 10¹². Optællingen dækker hele intervallet, og de første 2.000 primtal vises. For eksempel er der 25 primtal mellem 1 og 100 og 78.498 under en million.