Sito Eratostenesa

Algorytm Sito Eratostenesa

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

	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 usuwamy wszystkie jej wielokrotności większe od niej samej: 6,9,12,… przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

	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.

	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 aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

	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 liczba i której wielokrotność wykreślamy, będzie większa niż pierwiastek(n)

Dla danej liczby n wszystkie niewykreślone liczby mniejsze, bądź równe n 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ą 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ż pierwiastek(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.