Problemem liczb pierwszych zajmowali się matematycy od bardzo dawna. Jednym z nich był matematyk grecki Eratostenes z Cyreny, żyjący w III w. p.n.e. Wymyślona przez niego metoda wyznaczania wszystkich liczb pierwszych nie większych od zadanej liczby nosi do dziś nazwę sita Eratostenesa.

Aby sprawdzić, czy liczba naturalna n jest liczbą pierwszą, należy dzielić ją przez każdą taką liczbę k>1, gdzie k2≤n. Sposób ten nie jest najbardziej efektywną metodą, ponieważ trzeba wykonać dużą liczbę czasochłonnych dzieleń, tym większą, im większą wartość ma badana liczba.

Skoro łatwiej jest mnożyć niż dzielić, Eratostenes zamiast sprawdzać podzielność kolejnych liczb naturalnych, zaproponował usuwanie ze zbioru liczb naturalnych wielokrotności kolejnych liczb, które nie zostały wcześniej usunięte.

Odnajdziemy za pomocą sita Eratostenesa wszystkie liczby pierwsze z zakresu od 2 do 30.
Zapisujemy kolejno wszystkie liczby w tabeli.

Teraz bierzemy pierwszą liczbę z tabeli (2) i począwszy od następnej wykreślamy z niej wszystkie te liczby, które są przez nią podzielne.

Bierzemy kolejną liczbę (3) i począwszy od następnej wykreślamy z tabeli podzielne przez nią.

Kolejną liczbą w tabeli jest 5. Postępujemy jak poprzednio.

W tym momencie możemy zakończyć nasze poszukiwania. Algorytm "mówi", że kolejne wykreślania należy powtarzać, nie dalej jak do liczby będącej zaokrąglonym w dół pierwiastkiem zakresu. U nas jest to:

po zaokrągleniu w dół otrzymujemy 5. W tabeli zostały już tylko liczby pierwsze.

#include <iostream>
#include <cmath>

using namespace std;
int main ()
{
	int i, w, n, *tablica;
	
	cout << "Podaj n: ";
	cin >> n;
	
	tablica = new int[n];
	int pomoc = sqrt(n);
	
	for (i = 2; i <= n; i++)
	tablica[i] = 1;
	
	for (i = 2; i <= pomoc; i++)
	{
		if (tablica[i] == 1)
		{
			w = 2 * i;	
			while (w <= n)
			{
				tablica[w] = 0;
				w = w + i;	
			}
		}
	}
	
	for (i = 2; i <= n; i++)
	{
		if (tablica[i]==1)
		cout << i << " ";	
	}
	
	delete [] tablica;
  return 0;
} 

Algorytm rozpoczyna się od przypisania każdemu indeksowi tablicy [2..n] wartości początkowej 1. Następnie rozpoczyna się szukanie wszystkich wielokrotności liczby i z przedziału [2..sqrt(n)]. Jednak przed tym sprawdzane jest, czy i-ty element tablicy jest oznaczony wartością 1. W następnych krokach pętli może zdarzyć się tak, że liczba i została już „odsiana” i przypisana mu została wartość 0, więc szukanie jej wielokrotności nie ma sensu, gdyż jeżeli dana liczba została już wcześniej „odsiana” to i jej wszystkie wielokrotności również. Wracając do warunku, gdy zostanie on spełniony, tzn. gdy i-ty element tablicy ma wartość 1, zaczęte zostanie szukanie wielokrotności liczby i, a mianowicie wszystkim wielokrotnością liczby i z przedziału [2..n] zostanie zmieniony element tablicy na wartość 0. Po sprawdzeniu wszystkich liczb z przedziału [2..sqrt(n)] należy wyświetlić wszystkie liczby z przedziału [2..n]. A dokładniej wyświetlić indeksy tablicy, których wartość jest równa 1.