Online generator prostih brojeva

Što je prost broj?

Prost broj je prirodni broj veći od 1, koji je djeljiv samo jedinicom i samim sobom. Najmanji prosti brojevi su 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Broj 2 je jedini parni prost broj – svi ostali parni brojevi su djeljivi s dva.

Brojevi poput 4 (= 2 × 2), 6 (= 2 × 3) ili 15 (= 3 × 5) nisu prosti brojevi – nazivamo ih složenim brojevima.

Kako generator funkcionira?

Za ispis svih prostih brojeva u rasponu koristimo Eratostenovo sito – jedan od najstarijih i najučinkovitijih algoritama, koji je opisao grčki matematičar Eratosten iz Kirene oko 240. godine pr. Kr.

Algoritam postupno prekrižava višekratnike svakog pronađenog prostog broja. Ono što ostane, jesu prosti brojevi. Cijeli se izračun odvija izravno u vašem pregledniku – nikakvi se podaci ne šalju na poslužitelj.

Za nasumični odabir, generator prvo sastavlja popis svih prostih brojeva u rasponu, a zatim iz njega nasumično odabire željeni broj pomoću kriptografski sigurnog generatora (crypto.getRandomValues()).

Značajke generatora

• Svi prosti brojevi – ispisuje svaki prost broj u zadanom rasponu (maks. 10 000)
• Nasumični odabir – odabire N nasumičnih prostih brojeva iz raspona (prikladno za velike raspone)
• Sortiranje – sortira rezultate uzlazno
• Razdjelnik – odaberite kako će brojevi biti razdvojeni prilikom kopiranja
• Brze postavke – najčešći rasponi jednim klikom

Gdje se koriste prosti brojevi?

Kriptografija i sigurnost

Prosti brojevi su temelj moderne kriptografije. Algoritmi poput RSA funkcioniraju na principu da je umnožak dva velika prosta broja lako izračunati, ali povratna dekompozicija na proste faktore je računalno vrlo zahtjevna.

• RSA šifriranje – ključevi se generiraju iz dva velika prosta broja
• Diffie-Hellman – razmjena ključeva putem prostog modula
• Hash funkcije – prosti brojevi kao magične konstante (SHA, MD5)

Matematika i znanost

• Teorija brojeva – osnovni građevni blokovi cijelih brojeva
• Goldbachova pretpostavka – svaki parni broj > 2 može se izraziti kao zbroj dvaju prostih brojeva (još nije dokazano)
• Riemannova hipoteza – jedan od Hilbertovih problema, tiče se raspodjele prostih brojeva

Praktična primjena

• Hash tablice – veličina tablice kao prosti broj smanjuje kolizije
• Generatori pseudonasumičnih brojeva – linearna kongruencija s prostim modulom
• Glazba i ritam – poliritmi s prostim duljinama ciklusa

Raspodjela prostih brojeva

Prosti brojevi su među prirodnim brojevima raspoređeni nepravilno, ali njihova gustoća opada s rastućim rasponom. To opisuje Teorem o prostim brojevima: broj prostih brojeva do N je približno N / ln(N).

Eratostenovo sito korak po korak

Raspon 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. Odaberi 2, prekriži višekratnike: 4, 6, 8, 10, 12...
2. Odaberi 3, prekriži višekratnike: 9, 15, 21, 27...
3. Odaberi 5, prekriži višekratnike: 25...
4. √30 ≈ 5.5 → gotovo

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

Eratostenovo sito u kodu

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

Česta pitanja (FAQ)