Primtallsgenerator online

Hva er et primtall?

Et primtall er et naturlig tall større enn 1 som kun er delelig med 1 og seg selv. De minste primtallene er 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Tallet 2 er det eneste partallprimtallet – alle andre partall er delelige med to.

Tall som 4 (= 2 × 2), 6 (= 2 × 3) eller 15 (= 3 × 5) er ikke primtall – vi kaller dem sammensatte tall.

Hvordan fungerer generatoren?

For å liste alle primtall i et område bruker vi Eratosthenes’ sil – en av de eldste og mest effektive algoritmene, beskrevet av den greske matematikeren Eratosthenes fra Kyrene rundt 240 f.Kr.

Algoritmen eliminerer gradvis multipler av hvert funnet primtall. Det som blir igjen, er primtallene. Hele beregningen foregår direkte i nettleseren din – ingen data sendes til serveren.

For tilfeldig utvalg setter generatoren først sammen en liste over alle primtall i området og velger deretter tilfeldig det ønskede antallet fra den ved hjelp av en kryptografisk sikker generator (crypto.getRandomValues()).

Generatorfunksjoner

• Alle primtall – viser hvert primtall i det angitte området (maks. 10 000)
• Tilfeldig utvalg – velger N tilfeldige primtall fra området (egnet for store områder)
• Sortering – sorter resultatene i stigende rekkefølge
• Skilletegn – velg hvordan tallene skal skilles ved kopiering
• Hurtigvalg – de vanligste områdene med ett klikk

Hvor brukes primtall?

Kryptografi og sikkerhet

Primtall er grunnlaget for moderne kryptografi. Algoritmer som RSA fungerer på prinsippet om at produktet av to store primtall er enkelt å beregne, men det er beregningsmessig svært krevende å faktorisere dem tilbake til primfaktorer.

• RSA-kryptering – nøkler genereres fra to store primtall
• Diffie-Hellman – nøkkelutveksling over en primtallsmodul
• Hash-funksjoner – primtall som magiske konstanter (SHA, MD5)

Matematikk og vitenskap

• Tallteori – de grunnleggende byggesteinene for heltall
• Goldbachs formodning – hvert partall > 2 kan uttrykkes som summen av to primtall (fortsatt ubevist)
• Riemann-hypotesen – et av Hilberts problemer, angår fordelingen av primtall

Praktisk bruk

• Hash-tabeller – tabellstørrelse som et primtall reduserer kollisjoner
• Pseudotilfeldige tallgeneratorer – lineær kongruens med en primtallsmodul
• Musikk og rytme – polyrytmer med primtallsbaserte sykluslengder

Fordelingen av primtall

Primtall er uregelmessig fordelt blant naturlige tall, men deres tetthet avtar med økende område. Dette beskrives av Primtallsteoremet: antall primtall opp til N er omtrent N / ln(N).

Eratosthenes’ sil trinn for trinn

Område 2–30:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

1. Velg 2, stryker multipler: 4, 6, 8, 10, 12...
2. Velg 3, stryker multipler: 9, 15, 21, 27...
3. Velg 5, stryker multipler: 25...
4. √30 ≈ 5.5 → ferdig

Primtall: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratosthenes’ sil i kode

JavaScript

function sieve(to) {
  const composite = new Uint8Array(to + 1);
  const primes = [];
  for (let p = 2; p <= to; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let j = p * p; j <= to; j += p) composite[j] = 1;
  }
  return primes;
}

Python

def sieve(n):
    composite = bytearray(n + 1)
    primes = []
    for p in range(2, n + 1):
        if not composite[p]:
            primes.append(p)
            for j in range(p * p, n + 1, p):
                composite[j] = 1
    return primes

Ofte stilte spørsmål (FAQ)