Primtallssjekker
Sjekk om et tall er et primtall og finn faktorene. Bruk denne gratis primtallssjekk til å teste et tall øyeblikkelig og finne alle primfaktorer. Ingen registrering.
Hva er et primtall?
Ett primtall er et naturlig tall større enn 1 som har eksakt to forskjellige faktorer: 1 og seg selv. De første primene er: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...
Prinsipper om primtall:
- 2 er det eneste jevne primtallet. Alle andre jevne tall er delbare med 2, så de har flere enn to faktorer.
- 1 er ikke et primtall etter moderne konvensjon. Utslutter 1 bevarer unikheten i primfaktorisering (Fundamental Theorem of Arithmetic).
- Primtall er uendelige. Euclid beviste dette rundt 300 f.Kr.: anta en endelig liste over alle primtall p₁, p₂, ..., pₙ. Så er tallet (p₁ × p₂ × ... × pₙ) + 1 enten primtall selv eller har et primfaktor ikke i listen — motsats. Derfor er listen uendelig.
- Etter hvert som tallene blir større, blir primtall mindre vanlige — men de stopper aldri. Det er 25 primtall under 100, 168 under 1 000 og 78 498 under 1 000 000.
Ett komposit tall er noen positivt heltall større enn 1 som ikke er primtall — det har minst en faktor utenom 1 og seg selv. Tallet 12 er komposit fordi 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. Hvert komposit tall har en unik primfaktorisering (Fundamental Theorem of Arithmetic).
Hva er det å sjekke om et tall er primt
Det finnes flere metoder for primtallstesting, fra enkel trial division til avanserte sannsynlighetsalgoritmer:
Trial Division (basismetode): Sjekk om noen heltall fra 2 til √n deler n jevnt. Hvis ingen gjør det, er n primtall. Du trenger bare å sjekke opp til √n fordi hvis n = a × b med a ≤ b, så a ≤ √n. Hvis ingen divisor finnes opp til √n, finnes ikke noen over √n heller.
Optimert trial division: Sjekk først om 2 deler, så bare ujevn tall. Videre: sjekk 2, 3, så bare tall av formen 6k±1 (siden alle primtall > 3 er av denne formen). Dette reduserer antallet tester med om lag 66% sammenlignet med naiv trial division.
| Tall | √n (appr) | Test divisorer opp til | Primtall? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Ja (ingen deler jevnt) |
| 91 | 9,54 | 2, 3, 5, 7 | Nei (7 × 13 = 91) |
| 1 009 | 31,76 | Opp til 31 | Ja (primtall) |
| 1 001 | 31,64 | Opp til 31 | Nei (7 × 11 × 13 = 1 001) |
| 7 919 | 88,99 | Opp til 89 | Ja (det 1 000. primtallet) |
For store tall (hundrevis av sifre) er trial division komputasjonelt uhyre vanskelig. Avanserte tester som Miller-Rabin primtallstesten (sannsynlighetsbasert, brukt i kryptografi) og AKS primtallstesten (deterministisk polynomiale tid, 2002) brukes i stedet.
Primfaktorisering
Hver kompositt tall kan skrives som et unikt produkt av primtall — dets primfaktorisering. Dette er garantert av Fundamental Theorem of Arithmetic. For å finne primfaktoriseringen, divider hver gang med den minste primfaktoren:
| Tall | Primfaktorisering | Factor tree-brytning |
|---|---|---|
| 12 | 2² × 3 | 12 → 4×3 → 2×2×3 |
| 60 | 2² × 3 × 5 | 60 → 4×15 → 2²×3×5 |
| 100 | 2² × 5² | 100 → 4×25 → 2²×5² |
| 360 | 2³ × 3² × 5 | 360 → 8×45 → 2³×3²×5 |
| 1,024 | 2¹⁰ | Alle primfaktorer er 2 |
| 2,310 | 2 × 3 × 5 × 7 × 11 | Produkt av de første 5 primene |
Primfaktorisering brukes til å finne største felles divisor (GCD) og minste felles måltall (LCM) av tall. GCD(12, 18) = 2² × 3? Nei — ta den minste potensen av delt prim: GCD = 2¹ × 3¹ = 6. LCM tar den største potensen: LCM(12, 18) = 2² × 3² = 36.
Forholdet mellom primtall og matematikk og teknologi
Primtall er "atomene" i aritmetikken — Fundamental Theorem of Arithmetic sier at hver positiv heltall større enn 1 er enten et primtall eller kan uttrykkes som et unikt produkt av primtall. Dette unikheten gjør at primtall er de irredundante byggsteinene av alle tall.
Modern internett-sikkerhet avhenger av primtall. RSA-kryptering (brukt for HTTPS, e-postkryptering og digitale underskrifter) genererer offentlige nøkler ved å multiplisere to store primtall p og q til n = p × q. Kryptering og dekryptering nøkler beregnes ved hjelp av modulær aritmetikk med n. Sikkerheten bygger på integer faktorisering problem: gitt n (et 2048-bit tall med ~617 desimaltall), finne p og q er computasjonelt uoppnåelig med dagens teknologi.
Diffie-Hellman nøkkelutveksling bruker store primmoduli for sikker nøkkelavtale. Når du kobler deg til en hjemmeside over HTTPS, beskytter primtall dine data i realtid.
Hash-tabeller bruker prim-størrelse tabeller for å minimere kollisjoner. Når en hash-funksjon mapper nøkler til bucket-indeks, brukes en prim-størrelse på bucket-er for å sikre bedre distribusjon fordi primtall har ingen faktorer som kunne skape systematiske kollisjonsmønster.
Pseudorandomt tallgeneratorer (PRNG) bruker primmoduli i lineær kongruensgeneratorer og andre algoritmer. Perioden (før repetisjon) av slike generatorer er ofte lik primmodulens størrelse minus 1.
Spesielle typer av primtall
Blant det uendelige settet av primtall, har visse undergrupper spesielle egenskaper eller betydning:
| Type | Definisjon | Eksempler |
|---|---|---|
| Twinnprimtall | Primtall som skiller med 2 | (3,5), (11,13), (17,19), (41,43) |
| Mersenne-primtall | Primtall av formen 2ⁿ − 1 | 3, 7, 31, 127, 8,191 |
| Fermat-primtall | Primtall av formen 2^(2ⁿ) + 1 | 3, 5, 17, 257, 65,537 |
| Sophie Germain-primtall | p og 2p+1 er også primtall | 2, 3, 5, 11, 23, 29 |
| Palindromiske primtall | Primtall som leses samme frem og tilbake | 11, 101, 131, 151, 181 |
| Trygge primtall | Primtall p hvor (p−1)/2 også er primtall | 5, 7, 11, 23, 47, 59 |
Mersenne-primtall (2ⁿ − 1) er spesielt viktige fordi de kan testes for primtall ved hjelp av den effektive Lucas-Lehmer-testen. GIMPS-prosjektet (Great Internet Mersenne Prime Search) utnytter distribuert datamaskin-kraft verden over for å finne nye Mersenne-primtall. Per 2024 er det største kjente Mersenne-primtallet 2^136,279,841 − 1, med over 41 millioner desimaltall.
Twinnprimtall (par som skiller med 2) er antatt å være uendelige (Twin Prime Conjecture), men dette er fortsatt ikke bevist — et av de mest berømte åpne problemene i matematikk. I 2013 beviste Yitang Zhang at det er uendelig mange primpar som skiller med maksimalt 70 millioner, som senere ble forbedret til 246.
Fordeling av Primtall
Primtall blir mindre vanlige jo større tallene blir, men deres fordeling følger statistiske mønster beskrevet av Primtallteoremet:
Det såkalte Primtallteoremet (bevist uavhengig av Hadamard og de la Vallée-Poussin i 1896) sier at antall primtall opp til N, notert π(N), er omtrent N / ln(N) for store N:
| N | Sannt π(N) | Approximert N/ln(N) | Tetthet |
|---|---|---|---|
| 100 | 25 | 21,7 | 1 i 4 |
| 1 000 | 168 | 144,8 | 1 i 6 |
| 10 000 | 1 229 | 1 085,7 | 1 i 8 |
| 100 000 | 9 592 | 8 685,9 | 1 i 10 |
| 1 000 000 | 78 498 | 72 382,4 | 1 i 13 |
| 1 000 000 000 | 50 847 534 | 48 254 942 | 1 i 20 |
Det såkalte Riemann-hypotesen — ett av Millenniumsproblemen med en $1 million belønning — angår nøyaktig fordeling av primtall. Den antar at alle ikke-trivielle nullpunktene av Riemanns zeta-funksjon har virkelighet 1/2. Dette er forbundet til hvordan "tilfeldig" primtallenes fordeling opptrer — hypotesen forutsier optimal regelmessighet i primtallsgapper.
Ofte stilte spørsmål
Er 1 et primtall?
Nei. Ved moderne matematisk konvensjon er 1 ikke primtall eller kompositt. Utenom 1 fra primtallene bevarte unikheten for primfaktorisering (Fondamentalteoremet for aritmetikken) – hvis 1 var primtall, ville hver tall ha uendelig mange faktoriseringer (f.eks. 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Historisk har noen matematikere regnet 1 som primtall, men moderne definisjonen inkluderer det ikke.
Hva er det største kjente primtallet?
Per 2024 er det største kjente primtallet 2^136,279,841 − 1 (et Mersenne-primtall), oppdaget i oktober 2024. Det har over 41 millioner sifre. The Great Internet Mersenne Prime Search (GIMPS)-prosjektet finner de fleste rekordprimene ved hjelp av distribuert datamaskin fra frivillige over hele verden. Disse enorme primene har ingen praktiske anvendelser – deres søk er bare matematisk utforskning.
Finnes det mønster i primtallene?
Primtall ser ujevnt ut, men mønster finnes. Alle primtall > 5 slutter på 1, 3, 7 eller 9 (aldrig 0, 2, 4, 5, 6 eller 8). Alle primtall > 3 er av formen 6k±1. Tvillingprim (som skiller med 2, som 11 og 13) ser ut til å fortsette evig (usikker Twin Prime-antagelse). Primetalleteoremet beskriver statistisk tettheten av primtall nær N som om lag 1/ln(N).
Er 2 et primtall?
Ja, 2 er primtall – og det er det eneste jevne primtallet. 2 har bare to faktorer (1 og 2), og oppfyller dermed definisjonen. Hvert annet jevne tall er delbart med 2, og er derfor kompositt. Primheten til 2 er en spesiell tilfelle som ofte må behandles separat i algoritmer og bevis.
Hvorfor brukes primtal i kryptering?
RSA-kryptering genererer en nøkkelpar ved: (1) å velge to store primtall p og q (hver 1024+ bit), (2) å beregne n = p×q, (3) å beregne krypteringsnøkkel e og dekrypteringsnøkkel d ved hjelp av modulær aritmetikk. Enhver kan kryptere med n og e (offentlig nøkkel), men bare eieren av p og q (eller d) kan dekode. Sikkerheten bygger på den computasjonelle vanskeligheten av å faktorisere n tilbake til p×q.
Hva er den raskeste måten å sjekke om et tall er primtall?
For små tall (opptil ~10^12): optimalisert prøving av deling bare opp til √n ved hjelp av mønsteret 6k±1. For mellomstore tall: Miller-Rabin-primitallitetstest med noen vitner er sannsynlig men meget rask. For meget store tall (kryptografiske størrelser, 1000+ sifre): sannsynlige tester som Miller-Rabin med mange tilfeldige vitner, eller AKS-testen for deterministisk bevis.
Hva er en primforskjell?
En primforskjell er forskjellen mellom to påfølgende primtall. Den minste primforskjellen er 1 (mellom 2 og 3), og alle andre påfølgende primtall har forskjeller på minst 2 (siden ett må være oddetall). Forskjellene vokser langsomt i gjennomsnitt: nær N er gjennomsnittsforskjellen mellom primtall om lag ln(N). Uvanlige store primforskjeller finnes – det finnes uendelig lange sekvenser av påfølgende kompositttall (n!+2, n!+3, ..., n!+n er alle kompositt for noen n).
Hva er faktorer av 100?
100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². Faktorer av 100 er 2 og 5. Dette faktoriseringen forklarer hvorfor 100 kan deles jevnt av 1, 2, 4, 5, 10, 20, 25, 50 og 100 – hver deler svarer til en kombinasjon av 2⁰˒¹˒² og 5⁰˒¹˒².
Hva er Goldbachs antagelse?
Goldbachs antagelse (1742) sier at hver jevn tall større enn 2 kan uttrykkes som summen av to primtall. Eksempler: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Den har blitt verifisert computasjonelt opp til 4×10^18, men er fortsatt usikkert. Den er en av de eldste og mest berømte usikre problemene i tallteori.
Hvor mange primtall finnes det?
Det finnes uendelig mange primtall – Euclid beviste dette rundt 300 f.Kr. Beviset ved motsats: hvis primtall var begrenset, ville produktet av dem pluss 1 være enten primtall eller ha et primfaktor ikke i den påståtte fullstendige listen, en motsats. Selv om primtall blir mindre tett på større tall, stopper de aldri. Det er 78,498 primtall under 1,000,000 og 5,761,455 primtall under 100,000,000.