Jak wyznaczyć wszystkie \( \pi(200) \) liczb pierwszych niewiększych od \( 200 \)? Jeszcze w czasach starożytnych Eratostenes opisał metodę postępowania rozwiązującą ten problem.
Algorytm Sita
- Wczytaj \( n \). Wypisz listę wszystkich liczb naturalnych od \( 2 \) do \( n \). Na początku wszystkie liczby są nieskreślone.
- Dopóki istnieje nieskreślona jeszcze liczba na naszej liście niewiększa od \( \sqrt{n} \) powtarzaj:
Weź pierwszą nieskreśloną liczbę \( p \) z listy i dodaj do zbioru znalezionych liczb pierwszych. Później skreśl liczbę \( p \) z listy i skreśl wszystkie wielokrotności liczby \( p \), które są jeszcze na liście.
- Wszystkie pozostałe, nieskreślone liczby z listy dodaj do zbioru znalezionych liczb pierwszych.
Wystarczy wykreślać wielokrotności liczb pierwszych, niewiększych od \( \sqrt{n} \), gdyż jeśli dowolna liczba \( m\leq n \) ma nietrywialny dzielnik (różny od 1 i niej samej), to \( m \) ma nietrywialny dzielnik pierwszy, niewiększy od \( \sqrt{n} \).