Sito Eratostenesa

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.

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)}$

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 poczynając od jej kwadratu ${\displaystyle 2^{2}=4,}$ to jest ${\displaystyle 4,6,8,\dots }$

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i wykreślamy wszystkie jej wielokrotności poczynając od ${\displaystyle 3^{2}=9,}$ czyli: ${\displaystyle 9,12,15,\dots }$ (przy czym niektóre liczby będą skreślane więcej niż raz, np. 18 jako wielokrotność 2 i wielokrotność 3).

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Według tej samej procedury postępujemy dla liczby 5, wykreślając ${\displaystyle 25=5^{2},30,35,\dots }$

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Następnie dla 7 wykreślamy: ${\displaystyle 49,56,\dots }$

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Wykreślanie powtarzamy do momentu, gdy kolejna wybrana liczba ${\displaystyle i}$ będzie większa niż ${\displaystyle {\sqrt {n}},}$ ponieważ pierwsza "kandydatka" do skreślenia będzie już poza zbiorem: ${\displaystyle i^{2}>\left({\sqrt {n}}\right)^{2}=n.}$

Wszystkie liczby z ${\displaystyle \{2,3,4,\dots ,n\},}$ które nie zostały wykreślone, są liczbami pierwszymi.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

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ększe niż ${\displaystyle {\sqrt {n}}{:}}$
  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.