Sito Eratostenesa
algorytm wyznaczania liczb pierwszych z zadanego przedziału / Z Wikipedii, wolnej encyclopedia
Sito Eratostenesa – algorytm wyznaczania wszystkich liczb pierwszych mniejszych od danej, czyli z zadanego przedziału [1]. Opiera się na eliminacji liczb złożonych.
Szybkie fakty Struktura danych, Czasowa ...
Przykładowe działanie Sita Eratostenesa | |
Struktura danych | |
---|---|
Złożoność | |
Czasowa |
|
Pamięciowa |
|
Zamknij
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.