Kalkulator liczb pierwszych

Liczba pierwsza to liczba naturalna większa od 1, która dzieli się tylko przez 1 i przez siebie. Kalkulator liczb pierwszych sprawdza to dla dowolnej liczby do 20 cyfr. Przy liczbie złożonej pokazuje jej rozkład na czynniki pierwsze, liczbę dzielników i ich listę, a przy każdej liczbie najbliższą mniejszą i większą liczbę pierwszą.

Każdą liczbę większą od 1 da się rozłożyć na iloczyn liczb pierwszych i to tylko w jeden sposób, jeśli nie liczyć kolejności czynników. To zasadnicze twierdzenie arytmetyki, które sprawia, że liczby pierwsze są czymś w rodzaju cegiełek, z których zbudowane są wszystkie inne. Jeśli potrzebujesz listy liczb pierwszych z przedziału, skorzystaj z generatora liczb pierwszych.

1. Wpisz liczbę. Wynik pojawia się w trakcie pisania, a spacje między grupami cyfr są pomijane.
2. Przeczytaj werdykt i szczegóły: rozkład, dzielniki, sąsiednie liczby pierwsze, a dla liczb pierwszych także ich numer w kolejności i parę bliźniaczą.
3. Przyciskami „Poprzednia pierwsza” i „Następna pierwsza” przejdziesz do sąsiedniej liczby pierwszej.

Na szerokim ekranie obok narzędzia widać dziewięć kolejnych liczb wokół sprawdzanej. Od razu widać, jak gęsto leżą liczby pierwsze w danym miejscu i z czego zbudowane są ich sąsiedzi.

Najprostsza metoda to dzielenie próbne. Liczbę n dzieli się kolejno przez 2, 3, 5, 7 i dalsze liczby, aż do pierwiastka z n. Dalej nie trzeba, bo gdyby n = a · b i oba czynniki były większe od √n, ich iloczyn przekroczyłby n. Jeśli żadne dzielenie nie wyjdzie bez reszty, liczba jest pierwsza.

Pracę skraca obserwacja, że każda liczba pierwsza większa od 3 ma postać 6k − 1 albo 6k + 1. Pozostałe liczby postaci 6k, 6k + 2, 6k + 3 i 6k + 4 dzielą się przez 2 albo 3. Wystarczy więc sprawdzić 2, 3, a potem 5, 7, 11, 13, 17, 19 i tak dalej.

Przykład: czy 221 jest pierwsza? Pierwiastek z 221 to niecałe 15, więc sprawdzamy 2, 3, 5, 7, 11 i 13. Dzielenie przez 13 daje 17, więc 221 = 13 · 17 i liczba jest złożona.

Dzielenie próbne jest za wolne dla liczb o 20 cyfrach, bo wymagałoby miliardów dzieleń. Kalkulator najpierw sprawdza małe dzielniki, a potem wykonuje test Millera-Rabina. Ten test dla ustalonego zestawu podstaw 2, 3, 5 i dalszych liczb pierwszych do 41 daje pewny wynik dla wszystkich liczb mniejszych od około 3,3 · 10²⁴, czyli z dużym zapasem dla 20 cyfr.

Prostszy test Fermata nie wystarcza, bo dają się mu oszukać liczby Carmichaela. Najmniejsza z nich to 561 = 3 · 11 · 17, która zachowuje się w tym teście jak liczba pierwsza. Test Millera-Rabina wykrywa takie liczby.

Rozkład na czynniki liczb złożonych kalkulator wyznacza metodą rho Pollarda. Dzięki niej nawet iloczyn dwóch dziesięciocyfrowych liczb pierwszych rozkłada się w ułamku sekundy. Dla znacznie większych liczb, takich jak klucze RSA o setkach cyfr, żadna znana metoda nie jest wystarczająco szybka i na tym opiera się bezpieczeństwo tego szyfru.

• Euklides w „Elementach” (ok. 300 r. p.n.e.) udowodnił, że liczb pierwszych jest nieskończenie wiele. Jeśli pomnożyć wszystkie znane i dodać 1, wynik nie dzieli się przez żadną z nich, więc musi istnieć liczba pierwsza spoza listy.
• Eratostenes z Cyreny w III wieku p.n.e. opisał sito, czyli wykreślanie wielokrotności kolejnych liczb z listy. Ta metoda nadal służy do tworzenia list liczb pierwszych.
• Liczby postaci 2^p − 1 nazywa się liczbami Mersenne’a. Największe znane liczby pierwsze są właśnie tej postaci. Liczba 2^{136 279 841} − 1, odkryta w październiku 2024 roku w projekcie GIMPS, ma 41 024 320 cyfr.
• Twierdzenie o liczbach pierwszych mówi, że liczb pierwszych nie większych od n jest w przybliżeniu n / ln n. Im dalej, tym rzadziej się pojawiają, choć nigdy się nie kończą.

Wiele pytań pozostaje otwartych. Hipoteza Goldbacha z 1742 roku mówi, że każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych, i do dziś nie ma dowodu. Nie wiadomo też, czy par liczb bliźniaczych jest nieskończenie wiele. W 2013 roku Yitang Zhang udowodnił, że nieskończenie wiele par liczb pierwszych różni się o mniej niż 70 milionów, a późniejsze prace obniżyły tę granicę do 246.