Sito Eratostenesa: jak znaleźć liczby pierwsze algorytmem

Idea: eliminujemy liczby złożone

Zamiast sprawdzać każdą liczbę osobno, sito działa odwrotnie: usuwa liczby, o których wiadomo, że są złożone. Wielokrotność liczby pierwszej p (poza samą p) ma dzielnik p, więc pierwsza być nie może. Po usunięciu wielokrotności wszystkich odpowiednich liczb pierwszych zostają tylko liczby pierwsze. Pojęcie liczby pierwszej i inne metody jej sprawdzania opisuje artykuł o liczbach pierwszych; tu chodzi o wypisanie wszystkich takich liczb w przedziale.

Algorytm jest przypisywany Eratostenesowi z Cyreny. Dwie obserwacje czynią go szybkim:

• Start od kwadratu. Wielokrotności p mniejsze niż p² mają mniejszy dzielnik pierwszy, więc zostały już wykreślone wcześniej. Wykreślanie zaczynasz zatem od p².
• Koniec na pierwiastku. Gdy kwadrat kolejnej niewykreślonej liczby przekracza n, nie ma już czego wykreślać. Wystarczy więc obsłużyć liczby nie większe niż √n.

Przebieg krok po kroku dla n = 30

Zapisz liczby od 2 do 30. Pierwiastek z 30 to około 5,48, więc wykreślanie prowadzisz tylko dla 2, 3 i 5; następna niewykreślona liczba, czyli 7, ma kwadrat 49, większy od 30.

W kroku 2 liczby 12, 18, 24 i 30 są wielokrotnościami 3, ale zostały wykreślone już w kroku 1, więc w tabeli ich nie ma. W kroku 3 wielokrotność 30 także była już wykreślona. Po zakończeniu zostaje dziesięć liczb: 2, 3, 5, 7, 11, 13, 17, 19, 23 i 29. To wszystkie liczby pierwsze nie większe niż 30.

Stan tablicy po każdym kroku:

Pseudokod

wejście: n
tablica jest[0..n], na początku wszystkie wartości prawda
jest[0] i jest[1] ustaw na fałsz
dla p od 2 do pierwiastka z n:
    jeśli jest[p] jest prawdą:
        dla w od p*p do n, co p:
            jest[w] = fałsz
wynik: wszystkie indeksy i, dla których jest[i] jest prawdą

Tablica logiczna zastępuje wykreślanie na kartce: „prawda” oznacza, że liczba nadal może być pierwsza, a „fałsz”, że jest złożona albo nie jest brana pod uwagę (0 i 1).

Implementacja w Pythonie

import math

def sito(n):
    jest = [True] * (n + 1)
    jest[0:2] = [False, False]          # 0 i 1 nie są pierwsze
    for p in range(2, math.isqrt(n) + 1):
        if jest[p]:
            for w in range(p * p, n + 1, p):
                jest[w] = False
    return [i for i, x in enumerate(jest) if x]

print(sito(30))

Program uruchomiony w Pythonie 3.13 wypisuje:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

To ten sam wynik, który wyszedł z ręcznego przebiegu. Funkcja math.isqrt zwraca całkowitą część pierwiastka, więc pętla zewnętrzna kończy się na ostatniej liczbie, której kwadrat nie przekracza n. Uruchomienie tej samej funkcji dla większych wartości daje 25 liczb pierwszych do 100, 168 do 1000 i 78498 do miliona.

Złożoność w prostych słowach

Czas. Każdą liczbę wykreślasz niewiele razy: tyle, ile ma różnych dzielników pierwszych, i to tylko tych nie większych od √n. Sumarycznie daje to liczbę kroków rzędu n · log log n. Funkcja log log n rośnie bardzo wolno, więc w praktyce czas jest prawie proporcjonalny do n: dziesięć razy większy przedział to niewiele więcej niż dziesięć razy więcej pracy.

Pamięć. Algorytm potrzebuje tablicy o rozmiarze n, czyli pamięci rzędu n. To główne ograniczenie: dla bardzo dużych n tablica może nie mieścić się w pamięci, dlatego stosuje się warianty działające na kolejnych fragmentach przedziału.

Dla porównania metoda dzielenia przez liczby pierwsze do √n sprawdza każdą liczbę osobno, więc przy szukaniu wszystkich liczb pierwszych w przedziale sito zwykle wypada lepiej. Przy sprawdzeniu jednej, dużej liczby sito jest zbędne, bo wystarczy test dzielników.

Typowe błędy

Zadania do samodzielnego rozwiązania

1. Wykonaj ręcznie sito dla n = 50. Dla których liczb p wykreślasz wielokrotności? Odpowiedź: 2, 3, 5 i 7, bo 7² = 49 ≤ 50, a 11² = 121 > 50. Zostaje 15 liczb pierwszych, od 2 do 47.
2. Dla n = 100 napisz, jaka jest ostatnia liczba p, dla której wykreślasz. Odpowiedź: 7, bo 11² = 121 > 100.
3. Zmień kod tak, żeby zwracał liczbę liczb pierwszych nie większych niż n, i sprawdź ją dla n = 100. Odpowiedź: 25.

Zobacz też: Algorytm, NWW i NWD, System binarny.