Testowanie pierwszości do sqrt(n)

Podstawową umiejętnością matematyczną jest sprawdzenie, czy pojedyncza liczba jest pierwsza. Liczba pierwsza ma dokładnie dwa dzielniki: jeden i samą siebie. Sprawdźmy to szybko. 🔍

Można próbować dzielić n przez każdą liczbę od 2 do n minus 1. To poprawne rozwiązanie, ale boleśnie wolne, gdy n jest duże.

Kluczowy wniosek jest następujący: wystarczy sprawdzać dzielniki do pierwiastka kwadratowego z n. Powyżej tej wartości nie może pojawić się żaden nowy czynnik.

Dzielniki występują w parach, których iloczyn jest równy n. Gdyby oba były większe od pierwiastka kwadratowego, ich iloczyn przekroczyłby n, co jest niemożliwe.

Należy iterować po i od 2, dopóki i razy i pozostaje mniejsze lub równe n. Użycie i*i pozwala uniknąć błędów zmiennoprzecinkowych funkcji sqrt dla dużych liczb całkowitych.

Liczby mniejsze od 2 nigdy nie są pierwsze, dlatego należy odrzucić je na początku. Taki warunek ochronny sprawia, że główna pętla pozostaje przejrzysta i poprawna.

Należy połączyć wszystkie elementy: odrzucić małe wartości, a następnie sprawdzać potencjalne dzielniki aż do pierwiastka. Każde dzielenie bez reszty oznacza, że n jest złożone.

Najpierw należy osobno sprawdzić 2, a następnie testować tylko liczby nieparzyste. Pomijanie liczb parzystych mniej więcej połowę pracy bez dodatkowej złożoności.

Ten test działa w czasie O(sqrt n). Dla pojedynczej liczby nie większej niż miliard to tylko około 30 000 prostych operacji.

Test z pierwiastkiem sprawdza się doskonale dla jednego lub kilku zapytań. Jeśli potrzebne jest sprawdzenie pierwszości całego zakresu, znacznie szybszy będzie algorytm sita.

Porównywanie z i*i zamiast użycia math.sqrt pozwala uniknąć błędów zaokrągleń, które mogą nieprawidłowo uznać graniczną liczbę za pierwszą lub złożoną.

Proszę przypomnieć sobie granicę, która sprawia, że ten test jest szybki.

Można już sprawdzać pierwszość jednej liczby w czasie O(sqrt n), odrzucać małe wartości, pomijać liczby parzyste i używać i*i, aby zachować dokładność. ✅