# Generator prostih brojeva

> Generirajte sve proste brojeve u zadanom rasponu ili nasumično odaberite N. Koristi Eratostenovo sito za brze izračune u pregledniku – bez servera i čekanja.

URL: https://acrafto.com/hr/generator-prostih-brojeva-online/

Tools are interactive browser apps; there is no public API, no endpoints to call and no server-side processing. To use a tool, open its HTML page in a browser.

## Š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).

| Raspon | Broj prostih brojeva |
| --- | --- |
| 1–10 | 4 |
| 1–100 | 25 |
| 1–1 000 | 168 |
| 1–10 000 | 1 229 |
| 1–100 000 | 9 592 |
| 1–1 000 000 | 78 498 |

## 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)

### Je li 1 prost broj?

Ne. Broj 1 se tradicionalno ne smatra prostim brojem. Razlog je matematički – kada bismo 1 smatrali prostim brojem, teorema o jedinstvenoj faktorizaciji bi izgubila valjanost.

### Je li 2 prost broj?

Da. Broj 2 je najmanji i ujedno jedini parni prost broj. Svi ostali parni brojevi su djeljivi s dva, dakle složeni.

### Koliko prostih brojeva postoji?

Beskonačno mnogo. Euklid je to dokazao oko 300. godine pr. Kr. elegantnim dokazom kontradikcijom: pretpostavimo da postoji konačan broj prostih brojeva. Njihov umnožak + 1 tada ne može biti djeljiv nijednim od njih – dakle, to je novi prost broj, kontradikcija.

### Što su prosti brojevi blizanci?

Prosti brojevi blizanci su parovi prostih brojeva koji se razlikuju za 2, na primjer (3, 5), (11, 13), (17, 19), (41, 43). Postoji li ih beskonačno mnogo, još je uvijek neriješeno pitanje matematike (Pretpostavka o prostim brojevima blizancima).

### Koliko brzo algoritam radi?

Eratostenovo sito ima vremensku složenost O(n log log n). Za raspon do 10 milijuna, izračun u pregledniku obično traje manje od 100 ms.

## Other languages

- Čeština (cs): [Generátor prvočísel](https://acrafto.com/cs/generator-prvocisel/) ([Markdown](https://acrafto.com/cs/generator-prvocisel/index.md))
- Slovenčina (sk): [Generátor prvočísel](https://acrafto.com/sk/generator-prvocisel/) ([Markdown](https://acrafto.com/sk/generator-prvocisel/index.md))
- English (en): [Prime Number Generator](https://acrafto.com/en/prime-number-generator/) ([Markdown](https://acrafto.com/en/prime-number-generator/index.md))
- Deutsch (de): [Primzahlgenerator](https://acrafto.com/de/online-primzahl-generator/) ([Markdown](https://acrafto.com/de/online-primzahl-generator/index.md))
- Français (fr): [Générateur de nombres premiers](https://acrafto.com/fr/generateur-nombres-premiers/) ([Markdown](https://acrafto.com/fr/generateur-nombres-premiers/index.md))
- Español (es): [Generador de números primos](https://acrafto.com/es/generador-numeros-primos-online/) ([Markdown](https://acrafto.com/es/generador-numeros-primos-online/index.md))
- Italiano (it): [Generatore di numeri primi](https://acrafto.com/it/generatore-numeri-primi/) ([Markdown](https://acrafto.com/it/generatore-numeri-primi/index.md))
- Português (pt): [Gerador de números primos](https://acrafto.com/pt/gerador-numeros-primos-online/) ([Markdown](https://acrafto.com/pt/gerador-numeros-primos-online/index.md))
- Nederlands (nl): [Priemgetallengenerator](https://acrafto.com/nl/online-priemgetalgenerator/) ([Markdown](https://acrafto.com/nl/online-priemgetalgenerator/index.md))
- Polski (pl): [Generator liczb pierwszych](https://acrafto.com/pl/generator-liczb-pierwszych/) ([Markdown](https://acrafto.com/pl/generator-liczb-pierwszych/index.md))
- Română (ro): [Generator numere prime](https://acrafto.com/ro/generator-numere-prime-online/) ([Markdown](https://acrafto.com/ro/generator-numere-prime-online/index.md))
- Magyar (hu): [Prímszám generátor](https://acrafto.com/hu/primszam-generator/) ([Markdown](https://acrafto.com/hu/primszam-generator/index.md))
- Ελληνικά (el): [Γεννήτρια πρώτων αριθμών](https://acrafto.com/el/gennitria-proton-arithmon-online/) ([Markdown](https://acrafto.com/el/gennitria-proton-arithmon-online/index.md))
- Български (bg): [Генератор на прости числа](https://acrafto.com/bg/generator-na-prosti-chisla-onlajn/) ([Markdown](https://acrafto.com/bg/generator-na-prosti-chisla-onlajn/index.md))
- Slovenščina (sl): [Generator praštevil](https://acrafto.com/sl/generator-prastevil/) ([Markdown](https://acrafto.com/sl/generator-prastevil/index.md))
- Eesti (et): [Algarvude generaator](https://acrafto.com/et/algarvude-generaator/) ([Markdown](https://acrafto.com/et/algarvude-generaator/index.md))
- Latviešu (lv): [Pirmskaitļu ģenerators](https://acrafto.com/lv/primskaitlu-generators/) ([Markdown](https://acrafto.com/lv/primskaitlu-generators/index.md))
- Lietuvių (lt): [Pirminių skaičių generatorius](https://acrafto.com/lt/pirminiu-skaiciu-generatorius/) ([Markdown](https://acrafto.com/lt/pirminiu-skaiciu-generatorius/index.md))
- Svenska (sv): [Primtalsgenerator](https://acrafto.com/sv/primtalsgenerator-online/) ([Markdown](https://acrafto.com/sv/primtalsgenerator-online/index.md))
- Dansk (da): [Primtalsgenerator](https://acrafto.com/da/primtal-generator-online/) ([Markdown](https://acrafto.com/da/primtal-generator-online/index.md))
- Suomi (fi): [Alkulukugeneraattori](https://acrafto.com/fi/alkuluku-generaattori/) ([Markdown](https://acrafto.com/fi/alkuluku-generaattori/index.md))
- Norsk (no): [Primtallsgenerator](https://acrafto.com/no/primtallsgenerator/) ([Markdown](https://acrafto.com/no/primtallsgenerator/index.md))
- Українська (uk): [Генератор простих чисел](https://acrafto.com/uk/generator-prostyh-chysel/) ([Markdown](https://acrafto.com/uk/generator-prostyh-chysel/index.md))
- Русский (ru): [Генератор простых чисел](https://acrafto.com/ru/generator-prostykh-chisel-onlayn/) ([Markdown](https://acrafto.com/ru/generator-prostykh-chisel-onlayn/index.md))
- Српски (sr): [Generator prostih brojeva](https://acrafto.com/sr/generator-prostih-brojeva-online/) ([Markdown](https://acrafto.com/sr/generator-prostih-brojeva-online/index.md))
- Македонски (mk): [Генератор на прости броеви](https://acrafto.com/mk/generator-na-prosti-broevi/) ([Markdown](https://acrafto.com/mk/generator-na-prosti-broevi/index.md))
- Bosanski (bs): [Generator prostih brojeva](https://acrafto.com/bs/generator-prostih-brojeva/) ([Markdown](https://acrafto.com/bs/generator-prostih-brojeva/index.md))
- Shqip (sq): [Gjenerator numrash të thjeshtë](https://acrafto.com/sq/gjenerator-numrash-te-thjeshte/) ([Markdown](https://acrafto.com/sq/gjenerator-numrash-te-thjeshte/index.md))
- Türkçe (tr): [Asal sayı bulucu](https://acrafto.com/tr/asal-sayi-olusturucu/) ([Markdown](https://acrafto.com/tr/asal-sayi-olusturucu/index.md))
- 日本語 (ja): [素数一覧・生成ツール](https://acrafto.com/ja/online-prime-number-generator/) ([Markdown](https://acrafto.com/ja/online-prime-number-generator/index.md))
- 한국어 (ko): [소수 구하기](https://acrafto.com/ko/prime-number-generator/) ([Markdown](https://acrafto.com/ko/prime-number-generator/index.md))
- العربية (ar): [مولد الأعداد الأولية](https://acrafto.com/ar/prime-number-generator/) ([Markdown](https://acrafto.com/ar/prime-number-generator/index.md))
- हिन्दी (hi): [अभाज्य संख्या जनरेटर](https://acrafto.com/hi/prime-generator/) ([Markdown](https://acrafto.com/hi/prime-generator/index.md))
- Bahasa Indonesia (id): [Generator bilangan prima](https://acrafto.com/id/generator-bilangan-prima-online/) ([Markdown](https://acrafto.com/id/generator-bilangan-prima-online/index.md))
- Tiếng Việt (vi): [Trình tạo số nguyên tố](https://acrafto.com/vi/bo-tao-so-nguyen-to-truc-tuyen/) ([Markdown](https://acrafto.com/vi/bo-tao-so-nguyen-to-truc-tuyen/index.md))
- ไทย (th): [หาจำนวนเฉพาะ](https://acrafto.com/th/prime-number-generator/) ([Markdown](https://acrafto.com/th/prime-number-generator/index.md))
- עברית (he): [מחולל מספרים ראשוניים](https://acrafto.com/he/prime-number-generator/) ([Markdown](https://acrafto.com/he/prime-number-generator/index.md))