Sito Eratostenesa - metoda wyszukiwania liczb pierwszych polegająca na wypisaniu wszystkich liczb naturalnych z przedziału od 2 do pewnej liczby, a następnie na wykreślaniu z tego zbioru liczb złożonych.
Sito Eratostenesa jest przykładem algorytmu działającego na zasadzie wyszukiwania wyczerpującego.
Działanie metody
Najpierw należy wypisać kolejno wszystkie liczby naturalne od 2 do n. Następnie oznacza się najmniejszą liczbę (na początku będzie to 2) jako liczbę pierwszą, jednocześnie wykreślając ze zbioru wszystkie jej wielokrotności. W kolejnym kroku znowu bierze się najmniejszą liczbę (pomijając wykreślone i te już rozpatrzone), oznacza ją jako pierwszą i wykreśla wszystkie jej wielokrotności.
Czynność tę powtarza się do momentu, w którym rozpatrywana liczba jest większa od pierwiastka z największej liczby w zbiorze (w tym przypadku oznaczonej jako n).
Wszystkie liczby, które nie zostały wykreślone, są liczbami pierwszymi.
Przykład
Szukamy liczb pierwszych mniejszych bądź równych 25. Najpierw trzeba wypisać wszystkie liczby naturalne od 2 do 24.
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25
Pierwszą liczbą jest liczba 2. Oznaczamy tę liczbę jako liczbę pierwszą, a następnie wykreślamy wszystkie jej wielokrotności (oprócz niej samej).
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16 , 17, 18, 19, 20, 21, 22, 23, 24, 25
W kolejnym kroku robimy to samo z liczbą 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
Idziemy dalej. Liczba 4 jest już wykreślona, wiec w następnym kroku analizujemy liczbę 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
Kolejną analizowaną liczbą byłaby liczba 7. Nie musimy jej już jednak rozpatrywać, gdyż .
Liczbami pierwszymi w tym zbiorze są więc liczby 2, 3, 5, 7, 11, 13, 17, 19 i 23.