Gdy trzeba znaleźć wszystkie liczby pierwsze w określonym przedziale, ręczne sprawdzanie każdej liczby szybko staje się niewygodne. Sito Eratostenesa pozwala zrobić to znacznie sprawniej, dlatego wyjaśniam jego zasadę działania, pokazuję przykład krok po kroku i dodaję prostą implementację w Pythonie.
Najważniejsze informacje o metodzie wyszukiwania liczb pierwszych
- Cel: znalezienie wszystkich liczb pierwszych od 2 do wybranej granicy.
- Zasada: wykreślanie wielokrotności kolejnych liczb pierwszych.
- Punkt startowy: dla liczby p wystarczy zacząć od p².
- Złożoność: około O(n log log n), przy pamięci O(n).
- Zastosowanie: nauka algorytmów, zadania programistyczne i przygotowanie tablic liczb pierwszych.
Na czym polega sito Eratostenesa
Metoda służy do wyznaczania liczb pierwszych w przedziale od 2 do n. Liczba pierwsza ma dokładnie dwa dzielniki: 1 oraz samą siebie. Wszystkie pozostałe liczby większe od 1 są złożone, czyli można je zapisać jako iloczyn mniejszych liczb.
Zamiast osobno badać podzielność każdej liczby, tworzymy listę kolejnych wartości i stopniowo usuwamy te, które na pewno nie są pierwsze. Najpierw wykreślamy wielokrotności 2, później 3, 5, 7 i kolejnych liczb, które nie zostały wcześniej usunięte. Po zakończeniu procesu pozostają wyłącznie liczby pierwsze.
Pomysł przypisuje się Eratostenesowi z Cyreny, uczonemu żyjącemu około III wieku p.n.e.. Jak na metodę powstałą w starożytności, jest zaskakująco praktyczna. Do dziś dobrze sprawdza się wszędzie tam, gdzie chcemy wygenerować wiele liczb pierwszych naraz.
Jak działa algorytm krok po kroku
Załóżmy, że chcemy znaleźć liczby pierwsze od 2 do 30. Zapisujemy wszystkie liczby w tym zakresie, a potem przechodzimy przez nie od najmniejszej. Liczba, która nie została wykreślona, jest pierwsza, więc wykreślamy jej wielokrotności.
- Zaczynamy od liczby 2. Zostawiamy ją, a wykreślamy 4, 6, 8, 10 i tak dalej.
- Przechodzimy do 3. Nie została wykreślona, więc jest pierwsza. Usuwamy 9, 12, 15, 18, 21, 24, 27 i 30.
- Liczba 4 jest już oznaczona jako złożona, dlatego ją pomijamy.
- Następna niewykreślona liczba to 5. Wykreślamy jej wielokrotności, zaczynając od 25.
- Liczby 6, 8, 9 i kolejne złożone pomijamy. Pozostają liczby pierwsze.
Wynik dla zakresu do 30 to 2, 3, 5, 7, 11, 13, 17, 19, 23 i 29. Nie trzeba wykreślać wielokrotności każdej liczby aż do końca listy. Wystarczy pracować z liczbami nie większymi niż pierwiastek z n, ponieważ każda większa liczba złożona ma już mniejszy dzielnik, który wcześniej ją oznaczył.
Dlaczego wykreślanie zaczyna się od kwadratu
Dla liczby 5 pierwsze potencjalne wielokrotności to 10, 15, 20, 25 i 30. Wartości 10, 15 oraz 20 zostały jednak wykreślone wcześniej jako wielokrotności 2 albo 3. Pierwszą wielokrotnością, której nie musieliśmy jeszcze oznaczyć, jest więc 5 × 5 = 25.
Ta obserwacja ma znaczenie także w kodzie. Rozpoczęcie od p² ogranicza liczbę powtórzeń i pokazuje, że algorytm nie wykonuje zbędnej pracy.
Przykład implementacji w Pythonie
Najprostsza wersja korzysta z tablicy wartości logicznych. Element o indeksie i mówi, czy liczba i nadal może być pierwsza. Na początku wszystkie liczby uznajemy za potencjalnie pierwsze, a potem zmieniamy oznaczenia przy wielokrotnościach.
def sito_eratostenesa(n):
pierwsza = [True] * (n + 1)
if n >= 0:
pierwsza[0] = False
if n >= 1:
pierwsza[1] = False
p = 2
while p * p <= n:
if pierwsza[p]:
for wielokrotnosc in range(p * p, n + 1, p):
pierwsza[wielokrotnosc] = False
p += 1
return [liczba for liczba in range(n + 1) if pierwsza[liczba]]
print(sito_eratostenesa(30))Program zwróci listę liczb pierwszych do 30. Warunki dotyczące indeksów 0 i 1 są ważne, ponieważ ani 0, ani 1 nie są liczbami pierwszymi. To jeden z najczęstszych błędów w pierwszych implementacjach.
W językach takich jak C++, Java czy JavaScript zasada pozostaje identyczna. Zmienia się tylko sposób utworzenia tablicy i przejścia po jej elementach. Sam algorytm dobrze nadaje się do nauki pętli, tablic, warunków oraz analizy wydajności.
Kiedy ta metoda jest lepsza od sprawdzania dzielników
Jeżeli chcemy ocenić jedną liczbę, na przykład 997, wystarczy sprawdzić jej dzielniki do wartości √997. W takim zadaniu pojedynczy test pierwszości może być prostszy niż tworzenie całej tablicy. Gdy jednak potrzebujemy wszystkich liczb pierwszych w zakresie, przesiewanie zwykle wygrywa.
| Metoda | Najlepsze zastosowanie | Główna zaleta | Ograniczenie |
|---|---|---|---|
| Sprawdzanie dzielników | Jedna lub kilka liczb | Nie wymaga dużej tablicy | Przy wielu liczbach wykonuje dużo powtórzeń |
| Sito Eratostenesa | Wszystkie liczby pierwsze do n | Szybko przygotowuje cały zakres | Potrzebuje pamięci proporcjonalnej do n |
| Test pierwszości | Badanie pojedynczych dużych wartości | Może działać bez przechowywania całej listy | Nie generuje automatycznie wszystkich liczb z przedziału |
W praktyce wybieram tę metodę wtedy, gdy zakres jest znany z góry i potrzebuję później wielokrotnie odpowiadać na pytanie, czy dana liczba jest pierwsza. Po jednorazowym przygotowaniu tablicy sprawdzenie zajmuje wtedy stały czas, bo wystarczy odczytać odpowiednią wartość.
Wydajność i ograniczenia rozwiązania
Dla zakresu do n algorytm ma złożoność czasową około O(n log log n), a pamięciową O(n). To bardzo dobry wynik dla generowania całej listy, ale tablica rośnie razem z granicą. Przy ogromnych zakresach zwykła wersja może zużywać zbyt dużo pamięci.
Przykładowo, zakres do miliona jest dla współczesnego komputera niewielki. Przy dziesiątkach czy setkach milionów elementów trzeba już zwrócić uwagę na typ tablicy, zużycie pamięci i czas wykonania. W takich sytuacjach stosuje się między innymi sito segmentowe, które przetwarza przedział kawałkami zamiast przechowywać wszystko naraz.
Nie warto też używać sita do szyfrowania ani do sprawdzania pojedynczej bardzo dużej liczby. To algorytm do masowego generowania liczb pierwszych w ograniczonym przedziale, a nie uniwersalny test dla dowolnych danych.
Przeczytaj również: Interpunkcja w języku polskim - Jak pisać poprawnie i unikać błędów?
Typowe błędy początkujących
- Traktowanie liczby 1 jako pierwszej.
- Rozpoczynanie wykreślania od 2p zamiast od p², co nie psuje wyniku, ale zwiększa liczbę operacji.
- Przekroczenie zakresu tablicy przy ostatniej wielokrotności.
- Brak obsługi małych wartości n, takich jak 0 i 1.
- Założenie, że każda niewykreślona liczba wymaga osobnego sprawdzania wszystkich dzielników.
Najlepiej przetestować program na małych przypadkach, na przykład dla n równego 1, 2, 10 i 30. Taki prosty zestaw szybko ujawnia błędną inicjalizację oraz pomyłki w granicach pętli.
Jak wykorzystać algorytm w nauce
Ten przykład jest dobrym ćwiczeniem, bo łączy intuicyjny pomysł z kilkoma ważnymi pojęciami informatycznymi. Uczeń widzi, że algorytm nie musi sprawdzać wszystkiego po kolei, jeśli potrafi wcześniej wykluczyć całe grupy przypadków.
Proponuję zacząć od ręcznego wykreślania liczb do 50, potem zapisać algorytm w pseudokodzie, a dopiero na końcu przejść do wybranego języka programowania. Dzięki temu kod nie jest mechanicznym przepisaniem gotowego rozwiązania, lecz wynika ze zrozumianej procedury.
Dobrym kolejnym zadaniem jest policzenie, ile liczb pierwszych znajduje się w zakresie, wypisanie tylko liczb pierwszych bliźniaczych, czyli par różniących się o 2, albo porównanie czasu działania sita z metodą sprawdzania dzielników. Takie modyfikacje pokazują, że zrozumienie mechanizmu jest cenniejsze niż zapamiętanie jednej funkcji.
Od wykreślonej tablicy do sprawnego myślenia algorytmicznego
Sito Eratostenesa jest przede wszystkim sposobem na szybkie znalezienie wszystkich liczb pierwszych do ustalonej granicy. Jego siła tkwi w eliminowaniu wielokrotności, a nie w wielokrotnym badaniu tych samych liczb.
Do nauki i typowych zadań programistycznych wystarczy klasyczna tablica logiczna. Gdy zakres staje się bardzo duży, trzeba uwzględnić pamięć i rozważyć wersję segmentową. Sam pomysł pozostaje jednak ten sam: odsiewamy liczby złożone, aż zostaną tylko te, których nie da się tak wyeliminować.
