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.

Algorytm

Ze zbioru liczb naturalnych z przedziału ${\displaystyle [2,n],}$ tj. ${\displaystyle \{2,3,4,\dots ,n\},}$ wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest ${\displaystyle 4,6,8,\dots }$

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: ${\displaystyle 6,9,12,\dots ,}$ przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

Według tej samej procedury postępujemy dla liczby 5.

Następnie dla 7 aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

Wykreślanie powtarzamy do momentu, gdy liczba ${\displaystyle i,}$ której wielokrotność wykreślamy, będzie większa niż ${\displaystyle {\sqrt {n}}.}$

Dla danej liczby ${\displaystyle n}$ wszystkie niewykreślone liczby mniejsze, bądź równe ${\displaystyle n}$ są liczbami pierwszymi.

Powyższy algorytm można zapisać w postaci następującego pseudokodu^[4]:

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ęcej niż ${\displaystyle {\sqrt {n}}{:}}$
  if A[i] = true:
    for j :=  2*i, 3*i, 4*i, ..., nie więcej niż n :
      A[j] := false
 
Wyjście: wartości i takie, że A[i] zawiera wartość true.

Przypisy

Linki zewnętrzne

• Animacja sita Eratostenesa