Sito Eratostenesa

Sprawdzanie każdej liczby po kolei algorytmem pierwiastkowym jest szybkie, ale gdy w zadaniu musimy znaleźć wszystkie liczby pierwsze z przedziału np. od 2 do 1 000 000, nawet metoda z pierwiastkiem zajmie bardzo dużo czasu.

Tu z pomocą przychodzi starożytny Grek, Eratostenes, który wymyślił Sito Eratostenesa. Jest to algorytm działający w oparciu o wykreślanie (odsiewanie) liczb, które na pewno nie są pierwsze.

Jak działa to sito?

Wyobraź sobie, że piszemy na kartce wszystkie liczby od 2 do N.

1. Zaczynamy od liczby 2. Zaznaczamy ją jako pierwszą (bo jest), a następnie "wykreślamy" wszystkie jej wielokrotności (4, 6, 8, 10...), bo skoro dzielą się przez 2, na pewno nie są pierwsze.
2. Bierzemy kolejną niewykreśloną liczbę, czyli 3. Zaznaczamy jako pierwszą i wykreślamy jej wielokrotności (6, 9, 12, 15...).
3. 4 jest wykreślone, więc idziemy dalej do 5.
4. 5 nie jest wykreślone. Oznaczamy jako pierwszą i wykreślamy jej wielokrotności.

Robimy to powtarzalnie (tak naprawdę wystarczy iterować do pierwiastka z N). Na sam koniec liczby, które pozostały na kartce niewykreślone – to liczby pierwsze!

Złożoność czasowa Sita to abstrakcyjne O(N log log N), co w praktyce oznacza, że algorytm jest ekstremalnie szybki i działa prawie liniowo.

Implementacja krok po kroku

Najlepiej zaimplementować Sito używając tablicy logicznej o rozmiarze N+1. Wartość True oznacza "liczba pierwsza", a False oznacza "wykreślona".

Python

def sito_eratostenesa(n):
    # Tworzymy listę pełną True o rozmiarze n+1
    # Zakładamy na początku, że wszystkie liczby są pierwsze
    pierwsze = [True] * (n + 1)
    
    # Zera i jedynki od razu skreślamy, bo z definicji nie są pierwsze
    pierwsze[0] = False
    pierwsze[1] = False
    
    i = 2
    # Przechodzimy liczby tylko do pierwiastka z n
    while i * i <= n:
        if pierwsze[i] == True:
            # Skoro i jest pierwsze, to wykreślamy jego wielokrotności
            # Zaczynamy od i*i, wykreślając co 'i' kroków
            for j in range(i * i, n + 1, i):
                pierwsze[j] = False
        i += 1
        
    # Wypisywanie liczb, które ocalały (zostały True)
    for k in range(2, n + 1):
        if pierwsze[k] == True:
            print(k, end=" ")

# Wywołanie znajdzie i wypisze liczby pierwsze od 2 do 30
sito_eratostenesa(30)

C++

#include <iostream>
#include <vector>
using namespace std;

void sitoEratostenesa(int n) {
    // Tworzymy wektor (tablicę) o wielkości n+1 wypełnioną true
    vector<bool> pierwsze(n + 1, true);
    
    // 0 i 1 nie są pierwsze
    pierwsze[0] = false;
    pierwsze[1] = false;
    
    // Lecimy do pierwiastka
    for (int i = 2; i * i <= n; i++) {
        if (pierwsze[i] == true) {
            // Wykreślamy wszystkie wielokrotności liczby i
            // Zaczynamy od i*i, zwiększamy skokowo co 'i'
            for (int j = i * i; j <= n; j += i) {
                pierwsze[j] = false;
            }
        }
    }
    
    // Wypisywanie wyników
    for (int k = 2; k <= n; k++) {
        if (pierwsze[k] == true) {
            cout << k << " ";
        }
    }
}

int main() {
    sitoEratostenesa(30);
    return 0;
}

[!TIP] Dla dociekliwych: Skąd wzięło się j = i * i ? Dlaczego pętlę wykreślającą zaczynamy od i * i, a nie od i * 2? Wyobraź sobie, że jesteśmy na kroku wykreślania dla cyfry 5. Jeśli zaczniemy od wielokrotności np. 5 * 2, to przecież 10 zostało już wykreślone w kroku dla liczby 2! Liczba 15 (5 * 3) została wykreślona w kroku dla liczby 3. Tak naprawdę pierwszą NIEWYKREŚLONĄ wielokrotnością 5 będzie dopiero 5 * 5! To genialna optymalizacja, która pomija zbędne, powtarzające się operacje.