Liczba pierwsza to liczba całkowita większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Liczby pierwsze to elementy składowe wszystkich liczb całkowitych — każdą liczbę całkowitą można wyrazić jako iloczyn liczb pierwszych.
Pierwsze 25 liczb pierwszych
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
Zauważ, że 2 jest jedyną parzystą liczbą pierwszą. Wszystkie inne liczby parzyste są podzielne przez 2.
Metoda 1: Podział próbny
Najprostszy sposób sprawdzenia, czy liczba jest pierwsza — sprawdź, czy jakakolwiek liczba aż do pierwiastka kwadratowego dzieli ją równomiernie.
Kluczowe spostrzeżenie: jeśli n ma współczynnik większy niż √n, ma również odpowiadający mu współczynnik mniejszy niż √n. Musisz więc sprawdzić tylko do √n.
Algorytm:
- Jeśli n < 2, nie jest liczbą pierwszą
- Jeśli n = 2, liczba pierwsza
- Jeśli n jest parzyste (z wyjątkiem 2), to nie jest liczbą pierwszą
- Sprawdź wszystkie liczby nieparzyste od 3 do √n
- Jeśli jakieś n dzieli równomiernie, nie jest liczbą pierwszą
- W przeciwnym razie, prime
Przykład: Czy 97 jest liczbą pierwszą?
√97 ≈ 9,85, więc sprawdź liczby pierwsze do 9: 2, 3, 5, 7
- 97 ÷ 2 = 48,5 (nie całość)
- 97 ÷ 3 = 32,33... (nie całość)
- 97 ÷ 5 = 19,4 (nie całość)
- 97 ÷ 7 = 13,86 (nie całość)
Nie znaleziono dzielników — 97 jest liczbą pierwszą.
Przykład: Czy 91 jest liczbą pierwszą?
√91 ≈ 9,54, sprawdź do 9: 2, 3, 5, 7
- 91 ÷ 7 = 13 (cała liczba!)
91 nie jest liczbą pierwszą — 91 = 7 × 13.
Metoda 2: Sito Eratostenesa
Sito Eratostenesa znajduje wszystkie liczby pierwsze aż do zadanej granicy. Jest szybki i elegancki, wynaleziony przez greckiego matematyka Eratostenesa około 240 roku p.n.e.
Aby znaleźć wszystkie liczby pierwsze aż do 50:
- Zapisz liczby od 2 do 50
- Zacznij od 2 (pierwsza liczba pierwsza). Skreśl wszystkie wielokrotności 2 (4, 6, 8...)
- Przejdź do następnej nieprzekreślonej liczby: 3. Skreśl wielokrotności 3 (9, 15, 21...)
- Następne nieskrzyżowane: 5. Skreśl wielokrotności 5 (25, 35...)
- Następne nieskrzyżowane: 7. Skreśl wielokrotności 7 (49...)
- Zatrzymaj się, gdy dojdziesz do √50 ≈ 7,07
- Wszystkie pozostałe nieprzekreślone liczby są liczbami pierwszymi
Pierwszy czas do 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Liczby pierwsze do 100: Pełna lista
| Zakres | liczby pierwsze |
|---|---|
| 1–10 | 2, 3, 5, 7 |
| 11–20 | 11, 13, 17, 19 |
| 21–30 | 23, 29 |
| 31–40 | 31, 37 |
| 41–50 | 41, 43, 47 |
| 51–60 | 53, 59 |
| 61–70 | 61, 67 |
| 71–80 | 71, 73, 79 |
| 81–90 | 83, 89 |
| 91–100 | 97 |
Jest 25 liczb pierwszych poniżej 100.
Szybkie testy podzielności
Zanim wykonasz pełne dzielenie, sprawdź poniższe zasady:
| Podzielne przez | Jeśli... |
|---|---|
| 2 | Ostatnia cyfra jest parzysta (0,2,4,6,8) |
| 3 | Suma cyfr podzielna przez 3 |
| 5 | Ostatnia cyfra to 0 lub 5 |
| 7 | Nie ma prostej reguły – po prostu podziel |
| 11 | Suma cyfr przemiennych podzielna przez 11 |
Przykład: Czy 143 jest liczbą pierwszą?
- Nawet ✓
- 1+4+3 = 8, niepodzielne przez 3 ✓
- Nie kończy się na 0 lub 5 ✓
- √143 ≈ 11,96, sprawdź do 11
- 143 ÷ 7 = 20,43 ✓
- 143 ÷ 11 = 13 — podzielne!
143 = 11 × 13. Nie jest liczbą pierwszą.
Dlaczego liczby pierwsze mają znaczenie
Kryptografia: szyfrowanie RSA — używane do zabezpieczania bankowości internetowej, protokołu HTTPS i poczty e-mail — opiera się na fakcie, że pomnożenie dwóch dużych liczb pierwszych jest łatwe, ale rozłożenie wyniku na czynniki pierwsze jest niezwykle trudne.
Informatyka: tabele skrótów, generatory liczb losowych i sumy kontrolne wykorzystują właściwości liczb pierwszych.
Czysta matematyka: Rozkład liczb pierwszych pozostaje jednym z najgłębszych nierozwiązanych problemów matematyki — Hipoteza Riemanna.
Ciekawe najważniejsze fakty
- Największa znana liczba pierwsza (stan na 2024 r.) ma ponad 41 milionów cyfr
- Liczby bliźniacze to liczby pierwsze różniące się o 2 (11 i 13, 17 i 19, 41 i 43)
- Istnieje nieskończenie wiele liczb pierwszych - udowodnił to Euklides około 300 roku p.n.e
- Hipoteza Goldbacha (nieudowodniona od 1742 r.): każda liczba parzysta > 2 jest sumą dwóch liczb pierwszych