Online generátor prvočísel

Čo je prvočíslo?

Prvočíslo je prirodzené číslo väčšie ako 1, ktoré je deliteľné iba jednotkou a samým sebou. Najmenšie prvočísla sú 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Číslo 2 je jediné párne prvočíslo – všetky ostatné párne čísla sú deliteľné dvoma.

Čísla ako 4 (= 2 × 2), 6 (= 2 × 3) alebo 15 (= 3 × 5) prvočísla nie sú – hovoríme im zložené čísla.

Ako generátor funguje?

Na výpis všetkých prvočísel v rozsahu používame Eratostenovo sito – jeden z najstarších a najefektívnejších algoritmov, ktorý opísal grécky matematik Eratostenes z Kyrény okolo roku 240 pred n. l.

Algoritmus postupne vyškrtáva násobky každého nájdeného prvočísla. Čo zostane, sú prvočísla. Celý výpočet prebieha priamo vo vašom prehliadači – žiadne dáta sa neposielajú na server.

Pre náhodný výber generátor najprv zostaví zoznam všetkých prvočísel v rozsahu a potom z neho náhodne vyberie požadovaný počet pomocou kryptograficky bezpečného generátora (crypto.getRandomValues()).

Funkcie generátora

• Všetky prvočísla – vypíše každé prvočíslo v zadanom rozsahu (max. 10 000)
• Náhodný výber – vyberie N náhodných prvočísel z rozsahu (vhodné pre veľké rozsahy)
• Zoradenie – výsledky zoraďte vzostupne
• Oddeľovač – zvoľte, ako budú čísla oddelené pri kopírovaní
• Rýchle predvoľby – najčastejšie rozsahy jedným kliknutím

Kde sa prvočísla používajú?

Kryptografia a bezpečnosť

Prvočísla sú základom modernej kryptografie. Algoritmy ako RSA fungujú na princípe, že súčin dvoch veľkých prvočísel je jednoduché vypočítať, ale spätný rozklad na prvočinitele je výpočtovo veľmi náročný.

• RSA šifrovanie – kľúče sú generované z dvoch veľkých prvočísel
• Diffie-Hellman – výmena kľúčov nad prvočíselným modulom
• Hašovacie funkcie – prvočísla ako magické konštanty (SHA, MD5)

Matematika a veda

• Teória čísel – základné stavebné kamene celých čísel
• Goldbachova hypotéza – každé párne číslo > 2 možno vyjadriť ako súčet dvoch prvočísel (doteraz nedokázané)
• Riemannova hypotéza – jeden z Hilbertových problémov, týka sa rozloženia prvočísel

Praktické použitie

• Hašovacie tabuľky – veľkosť tabuľky ako prvočíslo znižuje kolízie
• Generátory pseudonáhodných čísel – lineárne kongruencie s prvočíselným modulom
• Hudba a rytmus – polyrytmy s prvočíselnými dĺžkami cyklov

Rozloženie prvočísel

Prvočísla sú medzi prirodzenými číslami rozmiestnené nepravidelne, ale ich hustota klesá s rastúcim rozsahom. Toto opisuje Veta o prvočíslach: počet prvočísel do N je približne N / ln(N).

Eratostenovo sito krok za krokom

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

Eratostenovo sito v kóde

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)