Ciurul lui Eratostene

Pentru determinarea numerelor prime de la 2 până la o anumită valoare n se poate folosi o metodă numită “Ciurul lui Eratostene”. Această metodă presupune că la început toate numerele sunt prime. În momentul în care găsim un număr prim k, vom scoate toţi multiplii lui mai mici decât numărul n (2*k, 3*k, …) din mulţimea numerelor prime. Pentru a stoca dacă un număr este prim sau nu, în implementare se va folosi pentru fiecare număr până la n câte un bit care la început are valoarea 1. Astfel, dacă avem n numere, vor fi necesari (n+7)/8 octeti. În momentul în care găsim un număr prim, pentru toţi multipli lui vom seta bitul corespunzător pe 0.