Sito Eratostenesa

Sito Eratostenesa

Przykładowe działanie Sita Eratostenesa
Struktura danych	Tablica, lista
Złożoność
Czasowa	${\displaystyle \mathrm {O} (n\cdot \log \log(n))}$
Pamięciowa	${\displaystyle \mathrm {O} (n)}$

Sito Eratostenesa – algorytm wyznaczania wszystkich liczb pierwszych mniejszych od danej, czyli z zadanego przedziału ${\displaystyle [2,n]}$^[1]. Opiera się na eliminacji liczb złożonych.

Jest przypisywany Eratostenesowi z Cyreny, najpóźniej od XVIII wieku^[2].

Własności sita Eratostenesa mogą być użyte do oszacowania wartości funkcji pi (π) – dowodu nierówności ${\displaystyle \pi (x)<{\frac {x}{\log \log x}};}$ zrobił to w 1808 roku Adrien-Marie Legendre^[3].

Algorytm ten udoskonalono; powstały bardziej wydajne jak sito Atkina.