Przykładowe działanie Sita Eratostenesa | |
Struktura danych | |
---|---|
Złożoność | |
Czasowa |
|
Pamięciowa |
|
Sito Eratostenesa – algorytm wyznaczania wszystkich liczb pierwszych mniejszych od danej, czyli z zadanego przedziału [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 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 tj. wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest
2 | 3 | 5 | 7 | 9 | |||||
11 | 13 | 15 | 17 | 19 | |||||
21 | 23 | 25 | 27 | 29 | |||||
31 | 33 | 35 | 37 | 39 | |||||
41 | 43 | 45 | 47 | 49 | |||||
51 | 53 | 55 | 57 | 59 |
Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 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 | 5 | 7 | ||||||
11 | 13 | 17 | 19 | ||||||
23 | 25 | 29 | |||||||
31 | 35 | 37 | |||||||
41 | 43 | 47 | 49 | ||||||
53 | 55 | 59 |
Według tej samej procedury postępujemy dla liczby 5.
2 | 3 | 5 | 7 | ||||||
11 | 13 | 17 | 19 | ||||||
23 | 29 | ||||||||
31 | 37 | ||||||||
41 | 43 | 47 | 49 | ||||||
53 | 59 |
Następnie dla 7 aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.
2 | 3 | 5 | 7 | ||||||
11 | 13 | 17 | 19 | ||||||
23 | 29 | ||||||||
31 | 37 | ||||||||
41 | 43 | 47 | |||||||
53 | 59 |
Wykreślanie powtarzamy do momentu, gdy liczba której wielokrotność wykreślamy, będzie większa niż
Dla danej liczby wszystkie niewykreślone liczby mniejsze, bądź równe są liczbami pierwszymi.
2 | 3 | 5 | 7 | ||||||
11 | 13 | 17 | 19 | ||||||
23 | 29 | ||||||||
31 | 37 | ||||||||
41 | 43 | 47 | |||||||
53 | 59 |
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ż 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
- ↑ Eratostenesa sito, [w:] Encyklopedia PWN [dostęp 2021-10-02] .
- ↑ 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].
- ↑ Eratosthenes, sieve of (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2023-06-10].
- ↑ Eric W. Weisstein , Sieve of Eratosthenes, [w:] MathWorld, Wolfram Research [dostęp 2017-11-26] (ang.).