Generátor prvočísel online

Co je prvočíslo?

Prvočíslo je přirozené číslo větší než 1, které je dělitelné pouze jedničkou a sebou samým. Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Číslo 2 je jediné sudé prvočíslo – všechna ostatní sudá čísla jsou dělitelná dvěma.

Čísla jako 4 (= 2 × 2), 6 (= 2 × 3) nebo 15 (= 3 × 5) prvočísla nejsou – říkáme jim čísla složená.

Jak generátor funguje?

Pro výpis všech prvočísel v rozsahu používáme Eratosthenovo síto – jeden z nejstarších a nejefektivnějších algoritmů, který popsal řecký matematik Eratosthenés ze Kyrény kolem roku 240 př. n. l.

Algoritmus postupně vyškrtává násobky každého nalezeného prvočísla. Co zbyde, jsou prvočísla. Celý výpočet probíhá přímo ve vašem prohlížeči – žádná data se neposílají na server.

Pro náhodný výběr generátor nejprve sestaví seznam všech prvočísel v rozsahu a poté z něj náhodně vybere požadovaný počet pomocí kryptograficky bezpečného generátoru (crypto.getRandomValues()).

Funkce generátoru

• Všechna prvočísla – vypíše každé prvočíslo v zadaném rozsahu (max. 10 000)
• Náhodný výběr – vybere N náhodných prvočísel z rozsahu (vhodné pro velké rozsahy)
• Seřazení – výsledky seřaďte vzestupně
• Oddělovač – zvolte, jak budou čísla oddělena při kopírování
• Rychlé předvolby – nejčastější rozsahy jedním kliknutím

Kde se prvočísla používají?

Kryptografie a bezpečnost

Prvočísla jsou základem moderní kryptografie. Algoritmy jako RSA fungují na principu, že součin dvou velkých prvočísel je snadné spočítat, ale zpětné rozložení na prvočinitele je výpočetně velmi náročné.

• RSA šifrování – klíče jsou generovány z dvou velkých prvočísel
• Diffie-Hellman – výměna klíčů nad prvočíselným modulem
• Hashovací funkce – prvočísla jako magické konstanty (SHA, MD5)

Matematika a věda

• Teorie čísel – základní stavební kameny celých čísel
• Goldbachova domněnka – každé sudé číslo > 2 lze vyjádřit jako součet dvou prvočísel (dosud nedokázáno)
• Riemannova hypotéza – jeden z Hilbertových problémů, týká se rozložení prvočísel

Praktické použití

• Hash tabulky – velikost tabulky jako prvočíslo snižuje kolize
• Generátory pseudonáhodných čísel – lineární kongruence s prvočíselným modulem
• Hudba a rytmus – polyrhytmy s prvočíselnými délkami cyklů

Rozložení prvočísel

Prvočísla jsou mezi přirozenými čísly rozmístěna nepravidelně, ale jejich hustota klesá s rostoucím rozsahem. Toto popisuje Věta o prvočíslech: počet prvočísel do N je přibližně N / ln(N).

Eratosthenovo síto krok za krokem

Rozsah 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. Vyber 2, vyškrtni násobky: 4, 6, 8, 10, 12...
2. Vyber 3, vyškrtni násobky: 9, 15, 21, 27...
3. Vyber 5, vyškrtni násobky: 25...
4. √30 ≈ 5.5 → hotovo

Prvočísla: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratosthenovo síto v kódu

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

Časté otázky (FAQ)