Spletni generator praštevil - Poiščite in generirajte hitro

Kaj je praštevilo?

Praštevilo je naravno število, večje od 1, ki je deljivo le z 1 in samo s seboj. Najmanjša praštevila so 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Število 2 je edino sodo praštevilo – vsa ostala soda števila so deljiva z dvema.

Števila, kot so 4 (= 2 × 2), 6 (= 2 × 3) ali 15 (= 3 × 5), niso praštevila – imenujemo jih sestavljena števila.

Kako deluje generator?

Za izpis vseh praštevil v obsegu uporabljamo Eratostenovo sito – enega najstarejših in najučinkovitejših algoritmov, ki ga je opisal grški matematik Eratosten iz Kirene okoli leta 240 pr. n. št.

Algoritem postopoma prečrta večkratnike vsakega najdenega praštevila. Kar ostane, so praštevila. Celoten izračun poteka neposredno v vašem brskalniku – na strežnik se ne pošiljajo nobeni podatki.

Za naključni izbor generator najprej sestavi seznam vseh praštevil v obsegu, nato pa iz njega naključno izbere želeno število z uporabo kriptografsko varnega generatorja (crypto.getRandomValues()).

Funkcije generatorja

• Vsa praštevila – izpiše vsako praštevilo v določenem obsegu (največ 10.000)
• Naključni izbor – izbere N naključnih praštevil iz obsega (primerno za velike obsege)
• Razvrščanje – rezultate razvrstite naraščajoče
• Ločilo – izberite, kako bodo števila ločena pri kopiranju
• Hitre prednastavitve – najpogostejši obsegi z enim klikom

Kje se uporabljajo praštevila?

Kriptografija in varnost

Praštevila so temelj sodobne kriptografije. Algoritmi, kot je RSA, delujejo na principu, da je zmnožek dveh velikih praštevil enostavno izračunati, vendar je razgradnja nazaj na prafaktorje računalniško zelo zahtevna.

• RSA šifriranje – ključi se generirajo iz dveh velikih praštevil
• Diffie-Hellman – izmenjava ključev nad praštevilskim modulom
• Funkcije zgoščevanja (Hash) – praštevila kot magične konstante (SHA, MD5)

Matematika in znanost

• Teorija števil – osnovni gradniki celih števil
• Goldbachova domneva – vsako sodo število > 2 se lahko izrazi kot vsota dveh praštevil (še ni dokazano)
• Riemannova hipoteza – eden od Hilbertovih problemov, nanaša se na porazdelitev praštevil

Praktična uporaba

• Hash tabele – velikost tabele kot praštevilo zmanjšuje kolizije
• Generatorji psevdonaključnih števil – linearna kongruenca s praštevilskim modulom
• Glasba in ritem – poliritmi s praštevilskimi dolžinami ciklov

Porazdelitev praštevil

Praštevila so med naravnimi števili razporejena neenakomerno, vendar njihova gostota pada z naraščajočim obsegom. To opisuje Izrek o praštevilih: število praštevil do N je približno N / ln(N).

Eratostenovo sito korak za korakom

Obseg 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. Izberi 2, prečrtaj večkratnike: 4, 6, 8, 10, 12...
2. Izberi 3, prečrtaj večkratnike: 9, 15, 21, 27...
3. Izberi 5, prečrtaj večkratnike: 25...
4. √30 ≈ 5.5 → končano

Praštevila: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratostenovo sito v kodi

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

Pogosta vprašanja (FAQ)