Primtalsgenerator online

Vad är ett primtal?

Ett primtal är ett naturligt tal större än 1 som endast är delbart med 1 och sig själv. De minsta primtalen är 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Talet 2 är det enda jämna primtalet – alla andra jämna tal är delbara med två.

Tal som 4 (= 2 × 2), 6 (= 2 × 3) eller 15 (= 3 × 5) är inte primtal – vi kallar dem sammansatta tal.

Hur fungerar generatorn?

För att lista alla primtal inom ett intervall använder vi Eratosthenes såll – en av de äldsta och mest effektiva algoritmerna, beskriven av den grekiske matematikern Eratosthenes från Kyrene runt år 240 f.Kr.

Algoritmen korsar successivt ut multipler av varje hittat primtal. Det som återstår är primtal. Hela beräkningen sker direkt i din webbläsare – ingen data skickas till servern.

För slumpmässigt urval bygger generatorn först en lista över alla primtal i intervallet och väljer sedan slumpmässigt det önskade antalet med en kryptografiskt säker generator (crypto.getRandomValues()).

Generatorns funktioner

• Alla primtal – listar varje primtal i det angivna intervallet (max 10 000)
• Slumpmässigt urval – väljer N slumpmässiga primtal från intervallet (lämpligt för stora intervall)
• Sortering – sortera resultaten i stigande ordning
• Avgränsare – välj hur talen ska avgränsas vid kopiering
• Snabba förinställningar – de vanligaste intervallen med ett klick

Var används primtal?

Kryptografi och säkerhet

Primtal är grunden för modern kryptografi. Algoritmer som RSA bygger på principen att produkten av två stora primtal är lätt att beräkna, men att faktorisera tillbaka till primfaktorerna är beräkningsmässigt mycket krävande.

• RSA-kryptering – nycklar genereras från två stora primtal
• Diffie-Hellman – nyckelutbyte med primtalsmodul
• Hashfunktioner – primtal som magiska konstanter (SHA, MD5)

Matematik och vetenskap

• Talteori – de grundläggande byggstenarna för heltal
• Goldbachs förmodan – varje jämnt tal > 2 kan uttryckas som summan av två primtal (ännu obevisat)
• Riemannhypotesen – ett av Hilberts problem, rörande fördelningen av primtal

Praktisk användning

• Hashtabeller – storleken på tabellen som ett primtal minskar kollisioner
• Pseudorandomsgeneratorer – linjär kongruens med primtalsmodul
• Musik och rytm – polyrytmik med primtalslängder på cykler

Fördelning av primtal

Primtal är oregelbundet fördelade bland naturliga tal, men deras densitet minskar med ökande intervall. Detta beskrivs av Primtalssatsen: antalet primtal upp till N är ungefär N / ln(N).

Eratosthenes såll steg för steg

Intervall 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. Välj 2, kryssa ut multipler: 4, 6, 8, 10, 12...
2. Välj 3, kryssa ut multipler: 9, 15, 21, 27...
3. Välj 5, kryssa ut multipler: 25...
4. √30 ≈ 5.5 → klart

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

Eratosthenes såll i kod

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

Vanliga frågor (FAQ)