Sito Eratostenesa

Szablon:Algorytm infobox Sito Eratostenesa – algorytm wyznaczania wszystkich liczb pierwszych mniejszych od danej, czyli z zadanego przedziału $[2,n]$. Opiera się na eliminacji liczb złożonych.

Jest przypisywany Eratostenesowi z Cyreny, najpóźniej od XVIII wieku.

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

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

Algorytm

Ze zbioru liczb naturalnych z przedziału $[2,n],$ tj. $\{2,3,4,\dots ,n\},$ wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności poczynając od jej kwadratu $2^2=4,$ to jest $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 $3^2=9,$ czyli: $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 $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: $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 $i$ będzie większa niż $\sqrt{n},$ ponieważ pierwsza "kandydatka" do skreślenia będzie już poza zbiorem: $i^2>{\left(\sqrt{n}\right)}^2=n.$

Wszystkie liczby z $\{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:

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ż $\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.

Linki zewnętrzne

• Animacja sita Eratostenesa