Online Generator Prostih Brojeva

Šta je prost broj?

Prost broj je prirodan 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 paran prost broj – svi ostali parni brojevi su djeljivi sa dva.

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

Kako funkcionira generator?

Za prikaz svih prostih brojeva u rasponu koristimo Eratostenovo sito – jedan od najstarijih i najefikasnijih algoritama, koji je opisao grčki matematičar Eratosten iz Kirene oko 240. godine p.n.e.

Algoritam postepeno precrtava višekratnike svakog pronađenog prostog broja. Ono što preostane su prosti brojevi. Cijeli izračun se odvija direktno u vašem pregledniku – nikakvi podaci se ne šalju na server.

Za nasumičan odabir, generator prvo sastavlja listu svih prostih brojeva u rasponu, a zatim iz nje nasumično bira željeni broj koristeći kriptografski siguran generator (crypto.getRandomValues()).

Funkcije generatora

• Svi prosti brojevi – prikazuje svaki prost broj u datom rasponu (maks. 10 000)
• Nasumičan odabir – bira 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 osnova moderne kriptografije. Algoritmi poput RSA funkcioniraju na principu da je umnožak dva velika prosta broja lako izračunati, ali je obrnuto razlaganje na proste faktore računarski vrlo zahtjevno.

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

Matematika i nauka

• Teorija brojeva – osnovni građevinski elementi cijelih brojeva
• Goldbachova pretpostavka – svaki paran broj > 2 može se izraziti kao zbir dva prosta broja (još uvijek nedokazano)
• Riemannova hipoteza – jedan od Hilbertovih problema, tiče se distribucije prostih brojeva

Praktična upotreba

• Hash tabele – veličina tabele kao prost broj smanjuje kolizije
• Generatori pseudonasumičnih brojeva – linearna kongruencija s prostim modulom
• Muzika i ritam – poliritmovi s prostim dužinama ciklusa

Distribucija prostih brojeva

Prosti brojevi su raspoređeni nepravilno među prirodnim brojevima, ali njihova gustina opada s rastućim rasponom. Ovo 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, precrtaj višekratnike: 4, 6, 8, 10, 12...
2. Odaberi 3, precrtaj višekratnike: 9, 15, 21, 27...
3. Odaberi 5, precrtaj 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

Često postavljana pitanja (FAQ)