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

	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: ${\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.

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

	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ę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

1. Eratostenesa sito, [w:] Encyklopedia PWN [dostęp 2021-10-02] .
2. Jeff Miller, Sieve of Eratosthenes, [w:] Earliest Known Uses of Some of the Words of Mathematics (S) (ang.), MacTutor History of Mathematics archive, University of St Andrews, mathshistory.st-andrews.ac.uk [dostęp 2023-06-10].
3. Eratosthenes, sieve of (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2023-06-10].
4. Eric W.E.W. Weisstein Eric W.E.W., Sieve of Eratosthenes, [w:] MathWorld, Wolfram Research [dostęp 2017-11-26]  (ang.).

Linki zewnętrzne

• Animacja sita Eratostenesa

Encyklopedie internetowe (test pierwszości):

• Britannica: topic/sieve-of-Eratosthenes
• БРЭ: 4937342
• NE.se: eratosthenes-såll
• DSDE: Eratosthenes'_si
• Hrvatska enciklopedija: 18198