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 – przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału ${\displaystyle [2,n]}$^[1].

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^[2]:

Wejście: liczba całkowita n > 1
 
Niech A będzie tablicą typów 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.

Zobacz też

• sito Atkina

Przypisy

Linki zewnętrzne

• Animacja sita Eratostenesa