Sito Eratostenesa krok po kroku. Jak znaleźć liczby pierwsze?

Jak szybko znaleźć wszystkie liczby pierwsze w wybranym zakresie, bez sprawdzania każdej z nich osobno? Sito Eratostenesa pokazuje, że pomysł sprzed ponad dwóch tysięcy lat nadal świetnie działa: pozwala systematycznie odrzucać liczby złożone i zostawić tylko te pierwsze. Wyjaśniam jego antyczne pochodzenie, działanie krok po kroku, przykład dla liczb do 30, zapis algorytmu oraz sytuacje, w których metoda ma swoje ograniczenia.

Skąd wzięła się metoda Eratostenesa

Autorem tej idei był Eratostenes z Cyreny, grecki matematyk, astronom, geograf i filozof żyjący około 276-194 roku p.n.e. Działał w świecie hellenistycznym, między innymi w Aleksandrii, gdzie kierował słynną biblioteką. Nie był więc wyłącznie teoretykiem liczb. Łączył matematykę z obserwacją świata, pomiarami Ziemi i porządkowaniem wiedzy.

Przypisywana mu metoda polega na „przesiewaniu” kolejnych liczb. Obraz jest bardzo prosty: zapisujemy liczby w szeregu, a potem usuwamy te, które da się zbudować przez mnożenie mniejszych liczb. Nieskreślone wartości pozostają liczbami pierwszymi.

To ważne także z historycznego punktu widzenia. W starożytności nie istniały komputery ani wygodne tablice obliczeniowe, dlatego liczyła się metoda ograniczająca liczbę koniecznych sprawdzeń. Eratostenes nie szukał pojedynczej liczby pierwszej, lecz uporządkowanego sposobu na znalezienie całej ich serii.

Jak działa przesiewanie liczb

Liczba pierwsza ma dokładnie dwa dodatnie dzielniki: 1 i samą siebie. Liczby 4, 6, 8 czy 9 odpadają, ponieważ można je podzielić także przez inne liczby. Algorytm korzysta z tego faktu i usuwa wszystkie wielokrotności znanych już liczb pierwszych.

1. Zapisuję liczby od 2 do wybranej granicy.
2. Wybieram najmniejszą nieskreśloną liczbę, czyli 2.
3. Skreślam jej wielokrotności większe od niej samej.
4. Przechodzę do kolejnej nieskreślonej liczby, czyli 3, i powtarzam działanie.
5. Kończę, gdy wybrana liczba przekroczy pierwiastek kwadratowy z górnej granicy.

Przy liczbie 2 usuwamy 4, 6, 8, 10 i tak dalej. Przy liczbie 3 skreślamy 9, 12, 15, 18. Nie trzeba zaczynać od 3, 6, 9, ponieważ część tych wartości została już usunięta jako wielokrotności 2. Dlatego najsprawniej rozpocząć od p², gdzie p oznacza aktualną liczbę pierwszą.

Ta reguła oszczędza czas, ale przede wszystkim pokazuje elegancję całego pomysłu. Nie sprawdzamy ponownie tego, co zostało już logicznie wykluczone. Właśnie dlatego metoda jest znacznie wydajniejsza niż testowanie podzielności każdej liczby przez wszystkie mniejsze wartości.

Przykład działania dla liczb do 30

Na początku zapisujemy ciąg od 2 do 30. Liczba 2 pozostaje, ponieważ jest pierwsza, a jej wielokrotności usuwamy. Otrzymujemy między innymi skreślone wartości 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 i 30.

Pierwszą nieskreśloną liczbą po 2 jest 3. Pozostawiamy ją, a skreślamy jej wielokrotności, które nie zostały wcześniej usunięte: 9, 15 i 21. Liczby 6, 12, 18, 24 i 30 były już wielokrotnościami 2.

Następna liczba to 5. Jej pierwsza nowa wielokrotność w badanym zakresie to 25, więc usuwamy 25. Nie musimy przechodzić do 7, ponieważ 7 przekracza pierwiastek z 30. Pozostałe nieskreślone liczby są pierwsze.

Wynik wygląda następująco:

• Liczby pierwsze: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
• Liczby złożone: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30.

Najczęstsza pomyłka polega na uznaniu jedynki za liczbę pierwszą. 1 nie jest liczbą pierwszą, ponieważ ma tylko jeden dodatni dzielnik. Algorytm powinien więc rozpoczynać się od 2, a nie od 1.

Jak zapisać algorytm w prostym pseudokodzie

W programie każdej liczbie przypisuje się informację, czy nadal może być pierwsza. Na początku zakładamy, że wszystkie wartości od 2 do n są możliwe. Później oznaczamy jako złożone te, które są wielokrotnościami kolejnych liczb pierwszych.

utwórz tablicę od 0 do n
ustaw wartości od 2 do n jako prawda

dla p od 2 do pierwiastka z n:
    jeśli p jest oznaczone jako prawda:
        dla wielokrotności od p * p do n co p:
            oznacz ją jako fałsz

wypisz wszystkie liczby oznaczone jako prawda

W praktyce tablica może przechowywać wartości logiczne, na przykład „pierwsza” lub „złożona”. Dla n równego 100 wystarczy tablica o rozmiarze 101, a po zakończeniu odczytujemy liczby od 2 do 100, które nie zostały skreślone.

Złożoność czasowa klasycznej wersji wynosi około O(n log log n), a pamięciowa O(n). To oznacza, że metoda jest bardzo dobra, gdy chcę wygenerować wiele liczb pierwszych naraz. Jeśli muszę tylko sprawdzić jedną niewielką liczbę, prosty test dzielenia może być łatwiejszy do napisania.

Kiedy warto użyć sita, a kiedy wybrać inną metodę

Największą zaletą algorytmu jest jego cel. Służy do znalezienia całej listy liczb pierwszych w przedziale, a nie tylko do odpowiedzi na pytanie, czy jedna liczba jest pierwsza. Dla zakresu od 2 do 1000 jego działanie jest szybkie i czytelne nawet w prostym programie edukacyjnym.

Nie traktowałbym więc tej techniki jako uniwersalnego narzędzia do każdej sytuacji. Przy bardzo dużych zakresach pamięć potrzebna na tablicę może stać się problemem. Wtedy stosuje się między innymi sito segmentowe, które dzieli przedział na mniejsze części i przetwarza je kolejno.

Najczęstsze błędy podczas stosowania metody

• Uwzględnienie liczby 1: nie jest pierwsza i należy ją pominąć.
• Skreślanie od 2p: jest poprawne, ale mniej wydajne niż rozpoczęcie od p².
• Sprawdzanie aż do n: niepotrzebnie wydłuża działanie, ponieważ wystarczy dojść do √n.
• Usuwanie samej liczby p: liczba będąca podstawą przesiewania pozostaje nieskreślona.
• Pominięcie górnej granicy: trzeba ustalić, czy n należy do analizowanego przedziału.

W ćwiczeniach szkolnych często widzę jeszcze jeden problem: ktoś skreśla wielokrotności 2, ale później nie skreśla wielokrotności 3, bo uznaje, że skoro 3 jest nieparzysta, to nie trzeba jej analizować. To błąd. Nieparzystość nie oznacza pierwszości, czego dobrym przykładem jest 9, 15 albo 21.

Moja praktyczna rada jest prosta: najpierw rozpisz ręcznie zakres do 30 lub 50, a dopiero potem przenieś regułę do kodu. Taki mały przykład szybko pokazuje, czy poprawnie rozumiesz różnicę między liczbą pierwszą, jej wielokrotnością i liczbą już wcześniej skreśloną.

Dlaczego pomysł z Aleksandrii nadal ma znaczenie

Siła tej metody nie polega wyłącznie na szybkości. Pokazuje ona sposób myślenia typowy dla dobrej matematyki: zamiast badać każdy przypadek oddzielnie, wykorzystujemy strukturę powtarzających się zależności. Jedno odkrycie, że liczba jest pierwsza, pozwala od razu usunąć cały ciąg jej wielokrotności.

Dlatego algorytm jest dobrym wprowadzeniem do programowania, teorii liczb i analizy wydajności. Uczy też, że rozwiązanie stworzone w starożytności może nadal być praktyczne, jeśli trafnie opisuje problem. W tym przypadku starożytne „przesiewanie” wciąż pozostaje jednym z najczytelniejszych sposobów generowania liczb pierwszych w ustalonym zakresie.

Najważniejsze, by pamiętać o granicach jego zastosowania. Do umiarkowanych przedziałów klasyczna wersja jest świetna, do ogromnych zakresów potrzebuje usprawnień, a przy pojedynczej liczbie nie zawsze będzie najprostszym wyborem. Właśnie takie dopasowanie narzędzia do zadania sprawia, że idea Eratostenesa nie jest tylko ciekawostką z historii matematyki, lecz nadal użytecznym algorytmem.