Generator Prostih Brojeva Online

Šta je prost broj?

Prost broj je prirodan broj veći od 1, koji je deljiv 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 deljivi sa dva.

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

Kako generator funkcioniše?

Za ispis svih prostih brojeva u opsegu 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 ostane su prosti brojevi. Ceo proračun se odvija direktno u vašem pretraživaču – nikakvi podaci se ne šalju na server.

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

Funkcije generatora

• Svi prosti brojevi – navodi svaki prost broj u datom opsegu (maks. 10 000)
• Nasumičan odabir – bira N nasumičnih prostih brojeva iz opsega (pogodno za velike opsege)
• Sortiranje – sortira rezultate uzlazno
• Separator – odaberite kako će brojevi biti razdvojeni prilikom kopiranja
• Brza podešavanja – najčešći opsezi jednim klikom

Gde se koriste prosti brojevi?

Kriptografija i bezbednost

Prosti brojevi su osnova moderne kriptografije. Algoritmi poput RSA funkcionišu na principu da je proizvod dva velika prosta broja lako izračunati, ali je obrnuta dekompozicija na proste faktore računarski veoma zahtevna.

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

Matematika i nauka

• Teorija brojeva – osnovni gradivni elementi celih brojeva
• Goldbachova pretpostavka – svaki paran broj > 2 može se izraziti kao zbir dva prosta broja (još uvek nedokazano)
• Rimanova hipoteza – jedan od Hilbertovih problema, odnosi se na distribuciju prostih brojeva

Praktična primena

• Heš tabele – veličina tabele kao prost broj smanjuje kolizije
• Generatori pseudonasumičnih brojeva – linearna kongruencija sa prostim modulom
• Muzika i ritam – poliritmi sa prostim dužinama ciklusa

Raspodela prostih brojeva

Prosti brojevi su nepravilno raspoređeni među prirodnim brojevima, ali njihova gustina opada sa povećanjem opsega. Ovo opisuje Teorema o prostim brojevima: broj prostih brojeva do N je približno N / ln(N).

Eratostenovo sito korak po korak

Opseg 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

Česta pitanja (FAQ)