Primtallssjekker

Slik bruker du primtallssjekkeren

1. Skriv inn et Helt tall. Uttrykk godtas også: 2^61-1, 10^12+39, 20!+1 eller 3711.
2. Svaret vises mens du skriver. Trykk Sjekk for å gi faktoriseringen mer tid på et vanskelig tall.
3. Les av konklusjonen, Primtallsfaktorisering, Antall delere, Forrige primtall og Neste primtall. Panelet Hvorfor forklarer hvordan svaret ble funnet, og Kopier faktoriseringen kopierer produktet av primtall.
4. For å liste opp primtall fyller du ut Fra og Til under Primtall i et intervall og trykker List opp primtall.

Tall på opptil 2048 bit (omtrent 617 sifre) godtas, og alt kjører i nettleseren din.

Hva som gjør et tall til et primtall

Et primtall er et helt tall større enn 1 som bare kan deles på 1 og seg selv: 2, 3, 5, 7, 11, 13 … Et tall med andre delere er sammensatt, og det kan skrives på nøyaktig én måte som et produkt av primtall, primtallsfaktoriseringen (360 = 2³ × 3² × 5). Tallene 0 og 1 er verken primtall eller sammensatte, og 2 er det eneste primtallet som er partall.

Antall delere følger av faktoriseringen: legg til 1 på hver eksponent og multipliser. 360 = 2³ × 3² × 5 har (3 + 1)(2 + 1)(1 + 1) = 24 delere. Et primtall har alltid nøyaktig 2.

Slik fungerer testen

• Små tall (under én million) sjekkes med prøvedeling: hvis ingen primtall opp til kvadratroten går opp i tallet, er det et primtall. Man trenger ikke gå lenger, fordi et sammensatt tall alltid har en faktor som ikke er større enn kvadratroten.
• Større tall deles først på alle primtall under 1000 og kjøres deretter gjennom Miller–Rabin-testen. Med de 13 basene 2, 3, 5, …, 41 er denne testen bevist eksakt for alle tall under 3,3 × 10²⁴, som omfatter alle 64-biters heltall. For disse tallene er svaret sikkert.
• Over 3,3 × 10²⁴ brukes 25 baser, og et tall som består dem alle, meldes som et sannsynlig primtall. Sjansen for feil er under 1 av 10¹⁵, men det er ikke et matematisk bevis. Når testen feiler, er tallet helt sikkert sammensatt.

Slik faktoriseres tallene

Små faktorer finnes ved prøvedeling. Større sammensatte deler splittes med Pollards rho-algoritme (Brents variant), som finner faktorer på opptil omtrent 10 sifre på brøkdelen av et sekund. Vanskeligere tall, for eksempel produktet av to primtall på 15 sifre eller mer, kan ta mye lengre tid enn noen tidsgrense, så faktoriseringen stopper etter noen sekunder. Den siste faktoren merkes da som sammensatt, men ikke delt opp, og et nytt trykk på Sjekk gir den mer tid.

Primtall i et intervall

Intervalllisten bruker en segmentert Eratosthenes’ sil, som stryker ut multiplene av hvert primtall. Den godtar opptil 1 000 000 tall per intervall med en øvre grense på opptil 10¹². Antallet gjelder hele intervallet, og de første 2000 primtallene listes opp. Det finnes for eksempel 25 primtall mellom 1 og 100 og 78 498 under én million.