Wejście: liczba całkowita n > 1
Niech A będzie tablicą wartości logicznych indeksowaną liczbami całkowitymi od 2 do n początkowo wypełniona wartościami true
for i := 2, 3, 4, ..., nie większe niż if A[i] = true: for j := i*i, i*(i+1), i*(i+2), ..., nie większe niż n : A[j] := false
Wyjście: wartości i takie, że A[i] zawiera wartość true. Np. w języku Python: def sito_eratostenesa(n): if n < 2: return []
# Wstępnie oznaczamy wszystkie liczby pierwsze = [True] * (n + 1)
# Eliminujemy 0 i 1 pierwsze = pierwsze = False
# Eliminujemy wielokrotności kolejnych liczb pierwszych for i in range(2, int(n ** 0.5) + 1): if pierwsze[i]: for j in range(i * i, n + 1, i): pierwsze[j] = False
return [i for i in range(n + 1) if pierwsze[i]]
# Przykład użycia: print(sito_eratostenesa(50)) Przypisy
Linki zewnętrzne Animacja sita Eratostenesa
Kategoria:Algorytmiczna teoria liczb Kategoria:Liczby pierwsze Kategoria:Teoria podzielności