- 2 kwietnia 2026
- Posted by: Damian
- Category: Baza wiedzy
Liczby pierwsze stanowią fundament matematyki, od wieków inspirując badaczy swoją prostotą oraz głębokimi implikacjami. Już w starożytności liczby pierwsze odgrywały kluczową rolę w rozwijaniu matematycznej wiedzy oraz praktycznych zastosowań – od kryptografii po badania naukowe.
Co to jest liczba pierwsza?
Liczby pierwsze to liczby naturalne większe od 1, które są podzielne przez dwie wartości, czyli 1 oraz samą siebie. Przykładowo 3 jest liczbą pierwszą, bo można ją podzielić przez 1 oraz 3 (bez uzyskiwania reszty z dzielenia). Zbiór liczb pierwszych oznacza się czasem jako P.
Wartości większe od 1, ale posiadające większą liczbę dzielników, to liczby złożone – wynika to wprost z definicji liczb pierwszych. Natomiast liczby 0 i 1 nie są ani pierwsze, ani złożone.
Co ciekawe, istnieją także tak zwane liczby bliźniacze, czyli liczby pierwsze, między którymi różnica wynosi 2. Przykładowo są to liczby 3 i 5, 17 i 19, a także 101 i 103.
Czy liczba jest pierwsza – kalkulator
- Komunikat:
- Czy liczba jest pierwsza:
Gdy potrzebujesz listy liczb pierwszych z określonego zakresu, skorzystaj z kalkulatora obsługującego Sito Eratostenesa, dostępnego na naszej stronie.
Liczby pierwsze do 100
Liczby pierwsze do 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Liczby pierwsze do 1000
Liczby pierwsze do 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
Jak sprawdzić, czy liczba jest pierwsza – algorytm testu pierwszości
W celu sprawdzenia, czy konkretna liczba jest pierwsza, możesz wykorzystać prosty algorytm, który pomoże zautomatyzować cały proces.
Sprawdzanie liczb pierwszych – pseudokod i schemat blokowy
Poniżej znajduje się pseudokod algorytmu sprawdzania pierwszości liczb oraz jego opis linia po linii.
1 2 3 4 5 6 7 | funkcja czyPierwsza (liczba): jeżeli liczba < 2 wykonuj zwróć fałsz dla i = 2,3 … liczba - 1 wykonuj jeżeli liczba mod i = 0 wykonuj zwróć fałsz zwróć prawda |
Opis pseudokodu – test pierwszości
- 1 linia – definicja funkcji czyPierwsza, która przyjmuje jako argument sprawdzaną liczbę,
- 2 linia – instrukcja warunkowa sprawdzająca, czy liczba jest mniejsza niż 2 (bo liczby pierwsze mają zakres wartości od 2 w górę),
- 3 linia – zwracamy logiczny „Fałsz”, jeśli liczba jest mniejsza od 2, ponieważ taka wartość nie może być liczbą pierwszą,
- 4 linia – instrukcja rozpoczynająca pętlę, w której zmienna i będzie przyjmować wartości od 2 do liczba – 1,
- 5 linia – instrukcja warunkowa sprawdzająca, czy liczba jest podzielna przez i (czyli czy reszta z dzielenia liczby przez i wynosi 0),
- 6 linia – w momencie, gdy liczba posiada jakiś dzielnik inny od 1 oraz ona sama, zwracamy wartość logiczną „Fałsz”, bo wartość nie jest liczbą pierwszą,
- 7 linia – jeśli pętla się zakończyła, to zwracamy wartość logiczną „Prawda”, ponieważ nie znaleźliśmy żadnego dzielnika liczby, co sugeruje, że liczba jest liczbą pierwszą.
Sprawdzanie liczb pierwszych – Python, Java i C++
Python – test pierwszości
1 2 3 4 5 6 7 8 9 10 11 | def czyPierwsza(liczba): if liczba < 2: return False for i in range(2, liczba): # zwroc uwage ze w pythonie pętle wykonują się do podanej wartości -1, dlatego podajemy liczba zamiast liczba -1 if liczba % i == 0: return False return True if czyPierwsza (7): print ("Liczba jest pierwsza.") else: print ("Liczba nie jest pierwsza.") |
C++ – test pierwszości
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include<iostream> using namespace std; bool czyPierwsza(int liczba) { if (liczba < 2) return false; for (int i = 2; i < liczba; ++i) { if (liczba % i == 0) return false; } return true; } int main() { if (czyPierwsza (7)) { cout << "Liczba jest pierwsza."; } else { cout << "Liczba nie jest pierwsza."; } return 0; } |
Java – test pierwszości
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class Main { public static boolean czyPierwsza(int liczba) { if (liczba < 2) { return false; } for (int i = 2; i < liczba; i++) { if (liczba % i == 0) { return false; } } return true; } public static void main(String[] args) { if (czyPierwsza(7)) { System.out.println("Liczba jest pierwsza."); } else { System.out.println("Liczba nie jest pierwsza."); } } } |
Zoptymalizowane sprawdzanie liczb pierwszych – pseudokod i schemat blokowy
Wcześniej opisana metoda wydaje się dobra, jednak jej złożoność wynosi O(n) – wciąż jest tu miejsce do optymalizacji. By to zrobić, wystarczy skorzystać z pewnej zależności, która pozwoli zmniejszyć liczbę wykonywanych iteracji (pętli).
Zauważmy, że w poprzedniej metodzie pętle są wykonywane od 2 do liczba – 1. Jednak taka liczba pętli nie jest potrzebna, bowiem przy wartościach od połowy tej liczby w górę niemożliwe jest, żeby znaleźć dzielnik (przykładowo w liczbie 16 nie istnieje żaden dzielnik większy od 8, czyli połowy tej wartości). Dlatego warto tu pójść o krok dalej i zdecydować się na wykonywanie iteracji zaledwie do pierwiastka sprawdzanej liczby (w przypadku liczby 16 do wartości 4).
Wynika to z prostej własności. Jeśli znajdziemy jakiś dzielnik liczby, to tak naprawdę znaleźliśmy również drugi, a więc dzielniki znalezione w zakresie do pierwiastka danej liczby wskazują na wszystkie dzielniki większe od tego pierwiastka. Poniżej znajdziesz przykłady wyjaśniające tę zasadę.
Przykład liczby 15:
Pierwszym dzielnikiem, jaki znajdziemy, jest 1. Odpowiadającym mu dzielnikiem jest 15, bo 15 : 1 = 15. Następny dzielnik to 3 i odpowiadający mu drugi dzielnik to 5, bo 15 : 3 = 5. Dalej nie ma sensu szukać dzielników, ponieważ znajdziemy już tylko te, które otrzymaliśmy przez podzielenie liczby, czyli 5.
Przykład liczby 16:
Pierwszy dzielnik to 1, a odpowiadający mu dzielnik to 16, bo 16 : 1 = 16. Następny to 2, a odpowiadający mu dzielnik to 8, bo 16 : 2 = 8. Kolejny to 4 i odpowiadający dzielnik to też 4, bo 16 : 4 = 4. Widzisz, co tu się stało? Znaleziony dzielnik oraz odpowiadający mu dzielnik są takie same! Taka sytuacja ma miejsce wtedy, kiedy liczba jest pierwiastkiem danej liczby.
Dalej możemy znaleźć już tylko dzielnik 8, który został wspomniany wcześniej, a więc pierwiastek danej liczby jest ostatnią wartością, którą należy sprawdzać – za nim wszystkie dzielniki będą tymi, które już znaleźliśmy. Jeśli pierwiastek nie jest dzielnikiem liczby, to sytuacja jest taka sama i też nie należy szukać dzielników dalej niż pierwiastek z liczby, bo i tak nic nie znajdziemy. Czyli iteracje są wykonywane tylko do pierwiastka danej wartości, a nie dalej.
Oznacza to, że złożoność naszej zoptymalizowanej wersji testu pierwszości to O(√n). Pozwala to na znaczne przyspieszenie działań w przypadku, gdy sytuacja jest pesymistyczna, a więc wartość jest duża i przy tym zalicza się do liczb pierwszych.
1 2 3 4 5 6 7 8 9 | funkcja czyPierwsza(liczba): jeżeli liczba < 2 wykonuj zwróć fałsz i ← 2 dopóki i * i ≤ liczba wykonuj jeżeli liczba mod i = 0 wykonuj zwróć fałsz i ← i + 1 zwróć prawda |
Opis pseudokodu – zoptymalizowany test pierwszości
- 4 linia – inicjalizacja zmiennej i wartością 2. Zmienna i będzie wykorzystywana do sprawdzania podzielności liczby przez kolejne liczby,
- 5 linia – pętla dopóki (odpowiednik while), która będzie wykonywana, dopóki potęga wartości i będzie mniejsza lub równa wartości zmiennej liczba. To sprawia, że pętla sprawdzi wszystkie możliwe dzielniki zmiennej liczba aż do jej pierwiastka kwadratowego,
- 8 linia – zwiększenie wartości zmiennej i o 1, aby przejść do sprawdzania następnej liczby jako potencjalnego dzielnika.
W pseudokodzie zastosowano i * i jako odpowiednik dla funkcji sqrt w językach programowania. Jest to alternatywne rozwiązanie w przypadku gdy nie ma gotowej funkcji pierwiastkującej. Jednak w poniższych kodach, zastosowano już odpowiednią funkcję umożliwiającą pierwiastkowanie liczby.
Zoptymalizowane sprawdzanie liczb pierwszych – Python, Java i C++
Python – zoptymalizowany test pierwszości
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | import math def czyPierwszaOpt (liczba): if liczba < 2: return False i = 2 for i in range(2,int(math.sqrt(liczba))+1): if liczba % i == 0: return False i += 1 return True if czyPierwszaOpt (7): print ("Liczba jest pierwsza.") else: print ("Liczba nie jest pierwsza.") |
C++ – zoptymalizowany test pierwszości
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include<iostream> #include <cmath> using namespace std; bool czyPierwszaOpt (int liczba) { if (liczba < 2) { return false; } for (int i = 2; i <= sqrt(liczba); i++) { if (liczba % i == 0) { return false; } } return true; } int main() { if (czyPierwszaOpt (7)) { cout << "Liczba jest pierwsza."; } else { cout << "Liczba nie jest pierwsza."; } return 0; } |
Java – zoptymalizowany test pierwszości
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public class Main { public static boolean czyPierwszaOpt (int liczba) { if (liczba < 2) { return false; } for (int i = 2; i <= Math.sqrt(liczba); i++) { if (liczba % i == 0) { return false; } } return true; } public static void main(String[] args) { if (czyPierwszaOpt(7)) { System.out.println("Liczba jest pierwsza."); } else { System.out.println("Liczba nie jest pierwsza."); } } } |
Uwaga: w standardowych językach programowania zazwyczaj dostępna jest funkcja licząca pierwiastek z liczby. Nie trzeba pamiętać wtedy o deklaracji i ani o jej inkrementacji. Jednak warto podkreślić, że funkcje pierwiastkujące nie są dostępne w zadaniach teoretycznych na maturze, chyba że zostały opisane w poleceniu!
Teraz już wiesz, jak wydajniej pisać ten podstawowy algorytm. Jeśli masz problem z jego zapamiętaniem, w celu optymalizacji zawsze możesz zastosować warunek „dla i = 2,3 … liczba div 2”, choć nie jest to aż tak wydajne. Czas wykonywania nadal zmniejszy się o połowę, a masz pewność, że algorytm zwróci poprawny wynik.
QUIZ – Sprawdź swoją wiedzę
Istnieją algorytmy sprawdzające pierwszość liczby wydajniejsze od rozwiązań przedstawionych w tym artykule, jednak są one dużo bardziej skomplikowane. Dlatego też ich przydatność na maturze jest ograniczona.
Jeśli interesuje Cię metoda znalezienia liczb pierwszych w danym zakresie wartości, możesz zdecydować się na wykorzystanie Sita Eratostenesa.
Najczęściej zadawane pytania o liczby pierwsze
Jaka jest największa liczba pierwsza?
Największa znana obecnie liczba pierwsza to 2136,279,841 − 1, która została odkryta w październiku 2024 roku w ramach projektu Great Internet Mersenne Prime Search (GIMPS). Jest to liczba Mersenne’a, która ma postać 2n − 1, gdzie n jest liczbą naturalną. Osiemdziesiąt pierwszych cyfr tej liczby to: 8816943235033265553939100378117397120735090660460656676412422969478414415990343.
Nie istnieje „największa liczba pierwsza”, a mowa jedynie o „największej obecnie znanej liczbie pierwszej”, czyli takiej, która została odkryta przez człowieka.
Ile jest liczb pierwszych?
Istnieje nieskończenie wiele liczb pierwszych, jako że jest nieskończenie wiele liczb naturalnych.
Czy liczby ujemne to liczby pierwsze?
Nie, liczby ujemne nie są liczbami pierwszymi. Liczba pierwsza musi być większa od 1 i mieć dokładnie dwa dzielniki: 1 i samą siebie. W przypadku liczb ujemnych żaden z tych warunków nie jest spełniony – są mniejsze od 1, a przy tym posiadają trzy dzielniki (1, samą siebie oraz liczbę przeciwną).
Do czego potrzebne są liczby pierwsze?
Liczby pierwsze są istotne w wielu obszarach matematyki i informatyki. Są one wykorzystywane między innymi w kryptografii, algorytmach szyfrowania, w generowaniu liczb losowych, a także w badaniach naukowych, takich jak analiza liczb czy teoria liczb.
Czy 0, 1 lub 2 jest liczbą pierwszą?
0 i 1 nie są liczbami pierwszymi, bo liczba pierwsza musi być większa od 1.
Natomiast 2 jest najmniejszą liczbą pierwszą, bo jest większa od 1, a także podzielna tylko przez 1 i samą siebie.
Jakie testy pierwszości są najpopularniejsze?
- Test Millera-Rabina – probabilistyczny test pierwszości, stosunkowo szybki i często wykorzystywany do sprawdzania pierwszości dużych liczb.
- Test AKS – deterministyczny test pierwszości, który działa w czasie wielomianowym, co oznacza, że jest w stanie sprawdzić pierwszość dużych liczb w efektywny sposób.
- Testy Fermata – testy oparte na małym twierdzeniu Fermata są stosunkowo proste do zrozumienia, ale mogą być mniej efektywne niż inne testy, zwłaszcza dla dużych liczb.
- Testy Lucas-Lehmera – są to testy używane do sprawdzania pierwszości liczb Mersenne’a, które mają postać 2n − 1, gdzie n jest liczbą pierwszą. Są one wyjątkowo efektywne dla takich liczb.
