W czasach starożytnych grecki uczoneny - Eratostenesa z Cyreny, znalazł sposób na znajdowanie liczb pierwszych. Sposób ten polegał na wyrzucaniu ze zbioru
liczb naturalnych, liczb będących wielokrotnościami poprzednich. "Oczyszczony" zbiór będzie zawierał same liczby pierwsze. Ta metoda została nazwana sitem
Eratostenesa.

Przykład
Odszukajmy wszystkie liczby pierwsze wśród 20 początkowych liczb naturalnych.

Początkowy zbiór:
{ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }

Najpierw usuwamy liczbę 1, ponieważ posiada tylko 1 dzielnik.

{ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }

Bierzemy liczbę 2 i usuwamy ze zbioru wszystkie jej wielokrotności. W ten sposób pozbyliśmy się liczb parzystych.

{ 2 3 5 7 9 11 13 15 17 19 }

Następną liczbą jest 3. Usuwamy ze zbioru wszystkie wielokrotności trójki. Pozostaną więc liczby niepodzielne przez 2 i przez 3.

{ 2 3 5 7 11 13 17 19 }

Wykonane - w zbiorze pozostały same liczby pierwsze.

Przeszukiwanie zbioru liczb kończymy na liczbie nie większej od pierwiastka największej liczby ze zbioru. W tym wypadku pierwiastek z 19 daje liczbę pomiędzy
4 a 5, więc nastepna liczba jaką mieliśmy sprawdzać ( 5 ) nie spełnia postawionego wcześniej warunku. Warunek bierze się stąd, iż liczby które pozostały
miałyby dzielniki większe od wcześniej sprawdzanych liczb ( 2 i 3 ). Więc najmniejszym takim dzielnikiem mogło być 5.
Mówiąc ogólniej - jeśli obecnie sprawdzaną liczbę oznaczymy jako x, to pierwszą liczbą jaką wyeliminujemy będzie x*x ( wszystkie mniejsze od x zostały wyeliminowane ). Jesli x*x >
najwieksza_liczba to musimy skończyć iterację, bo największa liczba ze zbioru jest mniejsza od następnej sprawdzanej. Po przekształceniu - sqrt(x*x) >
sqrt(najwieksza_liczba). ( Równość jest prawdziwa bo operujemy na liczbach naturalnych ).

Implementacja sita eratostenesa w c++ :

#include <stdio.h>
#include <conio.h>
#include <math.h>

void main(void)
{
int i,j,zakres,do_kad;
int tablica[10000];
printf("Podaj gorny zakres, do ktorego chcesz odnalezc liczby pierwsze\n");
scanf("%d",&zakres);
do_kad=floor(sqrt(zakres));

for (i=1; i<=zakres; i++) tablica[i]=i;
for (i=2; i<=do_kad; i++)
if (tablica[i]!=0)
for (j=i+1; j<=zakres; j++)
if (j%i==0) tablica[j]=0;

printf("Liczby pierwsze z zakresu od 1 do %d\n\n",zakres);

for (i=2; i<=zakres; i++) if (tablica[i]!=0) printf("%d, ",i);
getch();
}