Informatyka MIMUW

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

1. Wczytaj $n$. Wypisz listę wszystkich liczb naturalnych od $2$ do $n$. Na początku wszystkie liczby są nieskreślone.
2. 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.
3. 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}$.