Sprawdzanie liczb pierwszych

Jak sprawdzić, czy liczba jest pierwsza

1. Wpisz Liczba całkowita. Akceptowane są też wyrażenia: 2^61-1, 10^12+39, 20!+1 albo 3711.
2. Odpowiedź pojawia się już podczas pisania; przy trudnej liczbie naciśnij Sprawdź, aby dać rozkładowi więcej czasu.
3. Odczytaj werdykt, Rozkład na czynniki pierwsze, Liczba dzielników, Poprzednia liczba pierwsza i Następna liczba pierwsza. Panel Dlaczego wyjaśnia, jak doszło się do odpowiedzi, a Kopiuj rozkład kopiuje iloczyn liczb pierwszych.
4. Aby wypisać liczby pierwsze, wypełnij pola Od i Do w sekcji Liczby pierwsze w przedziale i naciśnij Wypisz liczby pierwsze.

Narzędzie przyjmuje liczby do 2048 bitów (ok. 617 cyfr), a wszystko działa w twojej przeglądarce – nic nie jest wysyłane na serwer.

Co to jest liczba pierwsza

Liczba pierwsza to liczba całkowita większa od 1, której jedynymi dzielnikami są 1 i ona sama: 2, 3, 5, 7, 11, 13… Liczba mająca inne dzielniki jest złożona i da się ją zapisać dokładnie w jeden sposób jako iloczyn liczb pierwszych – to jej rozkład na czynniki pierwsze (360 = 2³ × 3² × 5). Liczby 0 i 1 nie są ani pierwsze, ani złożone, a 2 to jedyna parzysta liczba pierwsza.

Liczba dzielników wynika z rozkładu: dodaj 1 do każdego wykładnika i pomnóż wyniki. 360 = 2³ × 3² × 5 ma (3 + 1)(2 + 1)(1 + 1) = 24 dzielniki. Liczba pierwsza ma zawsze dokładnie 2.

Jak działa test

• Małe liczby (poniżej miliona) są sprawdzane dzieleniem próbnym: jeśli żadna liczba pierwsza nie większa od pierwiastka kwadratowego nie dzieli liczby, liczba jest pierwsza. Dalej nie trzeba szukać, bo liczba złożona zawsze ma dzielnik nie większy niż jej pierwiastek.
• Większe liczby są najpierw dzielone przez wszystkie liczby pierwsze mniejsze od 1000, a potem poddawane testowi Millera–Rabina. Z 13 bazami 2, 3, 5, …, 41 test ten ma udowodnioną dokładność dla każdej liczby poniżej 3,3 × 10²⁴, czyli także dla wszystkich liczb 64-bitowych. Dla tych liczb odpowiedź jest pewna.
• Powyżej 3,3 × 10²⁴ używanych jest 25 baz, a liczba, która przejdzie je wszystkie, jest oznaczana jako prawdopodobnie pierwsza. Szansa błędu jest mniejsza niż 1 do 10¹⁵, ale nie jest to dowód matematyczny. Gdy test nie przejdzie, liczba jest na pewno złożona.

Jak liczby są rozkładane na czynniki

Małe czynniki są znajdowane dzieleniem próbnym. Większe złożone części rozkłada algorytm rho Pollarda (w wariancie Brenta), który znajduje czynniki mające do ok. 10 cyfr w ułamku sekundy. Trudniejsze liczby, np. iloczyn dwóch liczb pierwszych po 15 cyfr i więcej, mogą wymagać znacznie więcej czasu niż jakikolwiek limit, dlatego rozkład zatrzymuje się po kilku sekundach. Ostatni czynnik jest wtedy oznaczony jako złożony, ale nierozłożony, a ponowne naciśnięcie Sprawdź daje mu więcej czasu.

Liczby pierwsze w przedziale

Lista dla przedziału korzysta z segmentowanego sita Eratostenesa, które wykreśla wielokrotności kolejnych liczb pierwszych. Przyjmuje do 1 000 000 liczb w przedziale, z górną granicą do 10¹². Licznik obejmuje cały przedział, a wypisywanych jest pierwszych 2000 liczb pierwszych. Na przykład między 1 a 100 jest 25 liczb pierwszych, a poniżej miliona – 78 498.