Sito Eratostenesa jest algorytmem służącym do wyznaczenia wszystkich liczb pierwszych z zakresu od 2 do danego n. Działanie algorytmu polega na wykreślaniu z danego zbioru (2, 3, 4, ..., n) wszystkich wielokrotności kolejnych liczb (większych od nich), które nie zostały do tej pory wykreślone, przy czym wystarczy wziąć pod uwagę tylko liczby z zakresu od 2 do wartości całkowitej z ?n. Wszystkie liczby, które pozostaną niewykreślone, są liczbami pierwszymi.

Rys. 1. Działanie algorytmu na przykładowym zbiorze liczb. Wykreślamy wielokrotności kolejnych, niewykreślonych liczb (2, 3, 5) - analizujemy liczby od 2 do 5 (jest to wartość całkowitą ?30). Po zakończeniu działania algorytmu otrzymujemy zbiór liczb pierwszych z zakresu od 2 do 30 (liczby na żółtym tle).

Zastosowanie

Skutkiem działania algorytmu jest zbiór kolejnych liczb pierwszych z danego zakresu. Zbiór ten jest przydatny przy rozkładzie liczb na czynniki pierwsze, co z kolei jest wykorzystywane przy wyznaczaniu ilości dzielników liczby.

Implementacja

Najprościej rozwiązać problem, deklarując tablicę elementów z indeksami do liczby n i wykonać operację sprawdzania, które elementy tablicy nie zostały jeszcze wykreślone, za pomocą głównej pętli sprawdzającej oraz wykreślać wielokrotności owych liczb za pomocą kolejnej pętli. Poniżej implementacja zapisana za pomocą pseudokodu:

przypisz wszystkim elementom tablicy tablica początkową wartość logiczną TRUE

for od i = 2 do i = wartość całkowita z ?n do
{
	if tablica[i] == TRUE then
	{
		j = 2 * i     				//najmniejsza wielokrotność większa od danej liczby
		while j <= n do
		{
			tablica[j] = FALSE      //wykreślenie liczby
			j = j + i     			//przejdź do kolejnej wielokrotności
		}
	}
}