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ą.

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ść. ✅