Kalkulator liczby pierwszej

Liczba pierwsza to liczba naturalna większa od 1, która dzieli się tylko przez 1 i przez siebie samą. Przykłady: 2, 3, 5, 7, 11, 13, 17, 19. Liczba 2 jest jedyną parzystą liczbą pierwszą. Liczby takie jak 4, 6, 9, 15 nie są pierwsze, bo mają inne dzielniki.

Najprostszy sposób to próba dzielenia: dziel testowaną liczbę n przez wszystkie liczby od 2 do √n. Jeśli żadna nie jest dzielnikiem, liczba jest pierwsza. Dla n=17 sprawdzamy dzielniki do √17 ≈ 4,1 — żaden z 2, 3, 4 nie dzieli 17, więc 17 jest pierwsza.

Największa znana liczba pierwsza (stan na 2024 r.) to liczba Mersenne'a 2^136 279 841 − 1, odkryta przez projekt GIMPS. Liczy ona ponad 41 milionów cyfr. Poszukiwanie coraz większych liczb pierwszych to aktywna dziedzina matematyki i informatyki.

Euklides udowodnił ok. 300 r. p.n.e., że liczb pierwszych jest nieskończenie wiele. Twierdzenie o liczbach pierwszych mówi, że liczb pierwszych mniejszych od n jest w przybliżeniu n / ln(n). Poniżej 1 000 jest ich 168, poniżej 1 000 000 — aż 78 498.

Każdą liczbę naturalną większą od 1 można jednoznacznie (z dokładnością do kolejności) przedstawić jako iloczyn liczb pierwszych. Np. 12 = 2 × 2 × 3, 30 = 2 × 3 × 5, 100 = 2 × 2 × 5 × 5. Rozkład ten jest nazywany zasadniczym twierdzeniem arytmetyki.

Sito Eratostenesa to starożytny algorytm do wyznaczania wszystkich liczb pierwszych do podanej granicy. Zaczynamy od 2 i wykreślamy wszystkie wielokrotności każdej kolejnej niewykreślonej liczby. Niewykreślone liczby to liczby pierwsze. Metoda jest efektywna dla granic do kilku milionów.

Nie — 1 nie jest liczbą pierwszą. Historycznie zaliczano ją do pierwszych, ale współcześnie definicja wyklucza 1, bo jej włączenie zepsułoby zasadnicze twierdzenie arytmetyki (rozkład nie byłby jednoznaczny, np. 6 = 2×3 = 2×3×1 = 2×3×1×1…).

Liczby pierwsze są fundamentem kryptografii. Algorytm RSA opiera się na trudności rozkładania dużych liczb na czynniki pierwsze. Klucze kryptograficzne o długości 2048–4096 bitów są iloczynami dwóch ogromnych liczb pierwszych. Bez liczb pierwszych bezpieczna komunikacja internetowa byłaby niemożliwa.

Liczby bliźniacze to pary liczb pierwszych różniące się o 2, np. (3, 5), (11, 13), (17, 19), (29, 31), (41, 43). Hipoteza o liczbach bliźniaczych głosi, że takich par jest nieskończenie wiele, ale do dziś nie została udowodniona — to jeden z wielkich otwartych problemów matematyki.

Kalkulator używa algorytmu próbnego dzielenia do √n. Dla liczby n = 10⁹ = 1 000 000 000 sprawdza do ~31 623 dzielników — jest to bardzo szybkie. Dla sprawdzania pierwszości dużych liczb stosuje się szybsze testy probabilistyczne (Miller-Rabin) lub deterministyczne (AKS), ale dla celów edukacyjnych próbne dzielenie jest wystarczające.