Generator liczb pierwszych online

Co to jest liczba pierwsza?

Liczba pierwsza to liczba naturalna większa od 1, która dzieli się tylko przez 1 i przez siebie samą. Najmniejsze liczby pierwsze to 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Liczba 2 jest jedyną parzystą liczbą pierwszą – wszystkie inne liczby parzyste są podzielne przez dwa.

Liczby takie jak 4 (= 2 × 2), 6 (= 2 × 3) czy 15 (= 3 × 5) nie są liczbami pierwszymi – nazywamy je liczbami złożonymi.

Jak działa generator?

Do wyświetlania wszystkich liczb pierwszych w zakresie używamy sita Eratostenesa – jednego z najstarszych i najefektywniejszych algorytmów, który opisał grecki matematyk Eratostenes z Cyreny około 240 r. p.n.e.

Algorytm kolejno wykreśla wielokrotności każdej znalezionej liczby pierwszej. Co pozostaje, to liczby pierwsze. Całe obliczenia odbywają się bezpośrednio w Twojej przeglądarce – żadne dane nie są wysyłane na serwer.

W przypadku losowego wyboru generator najpierw tworzy listę wszystkich liczb pierwszych w zakresie, a następnie losowo wybiera z niej żądaną liczbę za pomocą kryptograficznie bezpiecznego generatora (crypto.getRandomValues()).

Funkcje generatora

• Wszystkie liczby pierwsze – wyświetla każdą liczbę pierwszą w podanym zakresie (max. 10 000)
• Losowy wybór – wybiera N losowych liczb pierwszych z zakresu (odpowiednie dla dużych zakresów)
• Sortowanie – sortuj wyniki rosnąco
• Separator – wybierz, w jaki sposób liczby będą oddzielone podczas kopiowania
• Szybkie ustawienia – najczęściej używane zakresy jednym kliknięciem

Gdzie używane są liczby pierwsze?

Kryptografia i bezpieczeństwo

Liczby pierwsze są podstawą współczesnej kryptografii. Algorytmy takie jak RSA działają na zasadzie, że iloczyn dwóch dużych liczb pierwszych jest łatwy do obliczenia, ale rozłożenie ich z powrotem na czynniki pierwsze jest obliczeniowo bardzo trudne.

• Szyfrowanie RSA – klucze są generowane z dwóch dużych liczb pierwszych
• Diffie-Hellman – wymiana kluczy z modułem pierwszoloczbowym
• Funkcje skrótu (Hash) – liczby pierwsze jako magiczne stałe (SHA, MD5)

Matematyka i nauka

• Teoria liczb – podstawowe elementy budulcowe liczb całkowitych
• Hipoteza Goldbacha – każda liczba parzysta > 2 może być wyrażona jako suma dwóch liczb pierwszych (nadal nieudowodniona)
• Hipoteza Riemanna – jeden z problemów Hilberta, dotyczy rozkładu liczb pierwszych

Praktyczne zastosowania

• Tablice skrótu (Hash) – rozmiar tablicy jako liczba pierwsza zmniejsza kolizje
• Generatory liczb pseudolosowych – kongruencja liniowa z modułem pierwszoloczbowym
• Muzyka i rytm – polirytmy z cyklami o długościach liczb pierwszych

Rozkład liczb pierwszych

Liczby pierwsze są rozmieszczone nieregularnie wśród liczb naturalnych, ale ich gęstość maleje wraz ze wzrostem zakresu. Opisuje to Twierdzenie o liczbach pierwszych: liczba liczb pierwszych do N wynosi w przybliżeniu N / ln(N).

Sito Eratostenesa krok po kroku

Zakres 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. Wybierz 2, wykreśl wielokrotności: 4, 6, 8, 10, 12...
2. Wybierz 3, wykreśl wielokrotności: 9, 15, 21, 27...
3. Wybierz 5, wykreśl wielokrotności: 25...
4. √30 ≈ 5.5 → gotowe

Liczby pierwsze: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Sito Eratostenesa w kodzie

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

Często zadawane pytania (FAQ)