Problem dotyczy osób, które zaczynają liczyć, programować albo po prostu rozwiązują zadania z matematyki i nagle pojawia się pytanie: „czy ta liczba jest pierwsza?”. Szuka się wtedy sposobu, który będzie szybki i nie będzie wymagał przekopywania się przez teorię liczb. Tutaj znajduje się kilka prostych metod sprawdzania pierwszości krok po kroku — od ręcznych trików po sensowny algorytm, który da się łatwo przepisać do kodu. Po drodze wyjaśnione są typowe pułapki (np. „1” i liczby ujemne) oraz to, kiedy test dzielenia „do końca” jest stratą czasu.
Co to znaczy, że liczba jest pierwsza (i na czym ludzie się potykają)
Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 oraz samą siebie. Tyle. W praktyce większość błędów bierze się nie z trudnych obliczeń, tylko z tego, że zapomina się o warunku „większa od 1”.
Najczęstsze potknięcia:
- 1 nie jest liczbą pierwszą (ma tylko jeden dodatni dzielnik: 1).
- 0 i liczby ujemne nie wchodzą do definicji liczb pierwszych (mówimy o liczbach naturalnych).
- 2 jest liczbą pierwszą i jest jedyną parzystą liczbą pierwszą — to ważne skrócenie w testach.
Jeśli liczba n ma dzielnik większy niż 1 i mniejszy niż n, to ma go też nie większy niż √n. Dlatego w praktyce nie trzeba sprawdzać wszystkich dzielników do n-1.
Najszybsze „filtry” na start: parzystość, 3 i proste reguły podzielności
Gdy sprawdza się pierwszość ręcznie, najpierw warto odsiać przypadki oczywiste. Taki filtr często kończy temat w 5 sekund.
Zaczyna się od dwóch pytań:
1) Czy n < 2? Jeśli tak, liczba nie jest pierwsza.
2) Czy n = 2 lub n = 3? Jeśli tak, liczba jest pierwsza.
Potem wchodzą proste reguły:
- Jeśli n jest parzysta i n ≠ 2, to nie jest pierwsza.
- Jeśli suma cyfr n jest podzielna przez 3 i n ≠ 3, to n nie jest pierwsza.
- Jeśli kończy się na 0 lub 5 i n ≠ 5, to n nie jest pierwsza.
To nie są pełne testy pierwszości (same z siebie nie potwierdzą, że liczba jest pierwsza), ale świetnie skracają sprawdzanie. W zadaniach szkolnych i prostych problemach programistycznych często wystarczą jako „sito wstępne”.
Metoda krok po kroku: sprawdzanie dzielników tylko do √n
To najbardziej klasyczny i jednocześnie sensowny sposób dla początkujących: sprawdzić, czy liczba ma dzielnik, ale nie męczyć się z testowaniem wszystkiego do n-1. Wystarczy dojść do pierwiastka.
Procedura wygląda tak:
- Jeśli n < 2 → niepierwsza.
- Jeśli n = 2 lub n = 3 → pierwsza.
- Jeśli n jest podzielne przez 2 lub 3 → niepierwsza.
- Sprawdzaj kolejne dzielniki d od 5 do √n (w praktyce co 2 lub co 6; o tym za chwilę).
- Jeśli znajdzie się dzielnik → niepierwsza. Jeśli nie → pierwsza.
Dlaczego wystarczy √n? Jeśli n = a · b i oba a oraz b byłyby większe niż √n, to iloczyn byłby większy niż n. To się nie może zgadzać, więc przynajmniej jeden dzielnik musi być ≤ √n. Proste i bardzo użyteczne.
Jak to policzyć „na piechotę” na przykładzie
Weźmy liczbę 221. Filtry:
Nie jest parzysta, suma cyfr 2+2+1 = 5 (nie dzieli się przez 3), nie kończy się na 5. Czyli trzeba sprawdzić dzielniki do √221. Pierwiastek z 221 to ok. 14,86, więc wystarczy sprawdzić dzielniki: 5, 7, 11, 13.
221 ÷ 5 – nie całkowite.
221 ÷ 7 – nie całkowite (7·31=217).
221 ÷ 11 – całkowite (11·20=220, więc 11·21=231, ale 221/11 = 20,09…? Sprawdzenie dokładne: 11·19=209, 11·20=220, zostaje 1 → nie).
221 ÷ 13 – 17 (13·17=221) → jest dzielnik, więc liczba nie jest pierwsza.
To ćwiczenie pokazuje dwie rzeczy: po pierwsze zakres jest krótki (do 14,86), po drugie warto sprawdzać mnożeniem „w głowie”, zamiast bawić się w długie dzielenie.
Wersja szybsza: sprawdzanie tylko liczb 6k ± 1
Po odrzuceniu podzielności przez 2 i 3, większość liczb i tak odpada. Da się to jeszcze przyspieszyć: każda liczba pierwsza większa od 3 ma postać 6k ± 1 (czyli jest o 1 mniejsza lub większa od wielokrotności 6). To nie jest „magiczny test” — to po prostu obserwacja, że liczby 6k, 6k±2, 6k+3 są podzielne przez 2 lub 3.
Jak to wykorzystać w praktyce? Zamiast sprawdzać wszystkie nieparzyste dzielniki, sprawdza się pary:
- d = 5 i d + 2 = 7
- d = 11 i 13
- d = 17 i 19
- …i tak dalej aż do √n
To oszczędza sporo pracy przy większych liczbach, a nadal jest proste do ogarnięcia. Nadal obowiązuje zasada: jeśli któryś dzielnik dzieli n bez reszty, n nie jest pierwsza.
Test pierwszości w kodzie: prosty i poprawny schemat
W programowaniu liczy się przewidywalność i brak „ukrytych” błędów na brzegach. Poniżej jest logika, którą da się przepisać do dowolnego języka (Python, JavaScript, C#, Java). Nie ma tu wodotrysków, ale jest poprawnie.
Minimalny algorytm (czytelny, wystarczający w większości zadań)
Założenie: sprawdzana jest liczba całkowita n. Wynik: true/false, czy jest pierwsza.
Logika:
- Jeśli n < 2 → false
- Jeśli n = 2 → true
- Jeśli n % 2 = 0 → false
- Sprawdzaj d od 3 do d·d ≤ n, krok 2 (tylko nieparzyste)
- Jeśli n % d = 0 → false, w przeciwnym razie po pętli → true
Zwraca uwagę warunek d·d ≤ n zamiast liczenia pierwiastka. W kodzie to często wygodniejsze i szybsze, a do tego unika problemów z zaokrągleniami na typach zmiennoprzecinkowych.
Wariant szybszy (6k ± 1) i kiedy ma sens
Jeśli sprawdzanie pierwszości ma się pojawiać często (np. w pętli, dla wielu liczb), wariant 6k ± 1 daje prosty zysk bez komplikowania życia. Schemat:
Po sprawdzeniu n < 2, przypadków n=2, n=3 oraz odrzuceniu podzielności przez 2 i 3:
- ustaw d = 5
- dopóki d·d ≤ n:
- sprawdź n % d oraz n % (d+2)
- zwiększ d o 6
Ten wariant nie „zgaduje” pierwszości — nadal dokładnie sprawdza dzielniki, tylko mądrzej wybiera kandydatów.
Kiedy proste metody przestają wystarczać (i co wtedy)
Jeśli sprawdzana jest jedna liczba rzędu miliona, metoda do √n działa świetnie. Jeśli sprawdzanych jest 100 000 liczb albo jedna liczba ma kilkaset cyfr, sytuacja się zmienia.
Dwa typowe scenariusze:
1) Dużo liczb w jakimś zakresie (np. wszystkie do 10 milionów). Wtedy lepiej użyć „sita” zamiast testować każdą osobno. Najpopularniejsze jest sito Eratostenesa — generuje listę liczb pierwszych w czasie dużo lepszym niż powtarzanie testu √n dla każdej liczby.
2) Bardzo duże liczby (kryptografia, liczby 100+ cyfr). Wtedy stosuje się testy probabilistyczne typu Miller–Rabin albo deterministyczne dla określonych zakresów. To już inna liga niż „proste metody”, ale warto wiedzieć, że takie narzędzia istnieją.
Dla liczb do okolic 10^12 test dzielenia do √n bywa nadal praktyczny w wielu zastosowaniach, o ile nie jest wykonywany miliony razy. Problemem nie jest sama metoda, tylko skala powtórzeń.
Najczęstsze błędy i szybka checklista poprawności
W zadaniach i w kodzie najczęściej psuje się nie matematyka, tylko szczegóły.
- Traktowanie 1 jako pierwszej (błąd definicji).
- Sprawdzanie dzielników aż do n/2 lub n-1 (zbyt wolno bez sensu).
- Brak osobnego potraktowania 2 (parzysta, a jednak pierwsza).
- Użycie √n na floatach i błędy przez zaokrąglenia (lepiej: d·d ≤ n).
Jeśli metoda ma być „pewna i prosta”, wystarczy zapamiętać: najpierw przypadki brzegowe, potem odrzucenie 2 i 3, a na końcu dzielenie tylko do √n. Reszta to optymalizacje.