Ciurul lui Eratostene

De ce contează?

Ai o sită prin care treci nisip: bobițele mari rămân sus, cele fine cad. Ciurul lui Eratostene face exact asta cu numerele — „cerne" și aruncă toate numerele compuse, iar ce rămâne neatins sunt numerele prime. În loc să verifici fiecare număr separat, le marchezi pe toate dintr-o singură trecere.

Ideea ciurului

Ca să găsești toate numerele prime până la n, nu verifici fiecare pe rând (ar fi lent). În schimb, pornești cu presupunerea că toate sunt prime și tai multiplii: 2 e prim → tai 4, 6, 8, …; 3 e prim → tai 6, 9, 12, …; și tot așa. Numerele care nu sunt tăiate niciodată sunt primele.

După cernere: primele rămân evidențiate (2,3,5,7,11,13), compusele sunt tăiate ca multipli ai unui prim mai mic.

Observația-cheie

Cheia eficienței: marcarea unui multiplu costă O(1), iar fiecare compus e marcat de puține ori (o dată pentru fiecare factor prim al lui). Pe total, munca e mult mai mică decât verificarea individuală a fiecărui număr.

Două optimizări care contează

Începe de la i·i. Când ajungi la primul i, multiplii 2·i, 3·i, … (i−1)·i au fost deja tăiați de factorii lor mai mici. Primul multiplu nou e i·i.
Oprește bucla exterioară la √n. Orice compus ≤ n are un factor prim ≤ √n, deci după ce marchezi multiplii primelor până la √n, toate compusele sunt deja tăiate.

Implementare C++

#include <iostream>
using namespace std;

const int N = 100;
bool compus[N + 1];   // compus[i] = true daca i NU este prim

int main() {
    for (int i = 2; i * i <= N; i++) {
        if (!compus[i]) {                       // i e prim
            for (int j = i * i; j <= N; j += i)
                compus[j] = true;               // taiem multiplii lui i
        }
    }

    for (int i = 2; i <= N; i++)
        if (!compus[i]) cout << i << " ";       // a ramas netaiat -> prim
    cout << "\n";
    return 0;
}

Vectorul global compus e inițializat automat cu false (toate „posibil prime"). La final, indicii rămași false sunt numerele prime.

Complexitate

Aspect	Valoare
Timp	O(n log log n) — practic aproape liniar
Spațiu	O(n) — un bit/bool pentru fiecare număr

Comparat cu verificarea fiecărui număr separat (O(n√n)), ciurul e dramatic mai rapid pentru a găsi toate primele dintr-un interval.

Vizualizare

Urmărește cum fiecare prim își taie multiplii pornind de la i·i, iar numerele care rămân neatinse după cernere sunt exact numerele prime:

Greșeli frecvente

Greșeala 1 — pornești de la 2·i: funcționează, dar faci muncă inutilă marcând multipli deja tăiați. Pornește de la i·i.

Greșeala 2 — tratezi 0 și 1 ca prime: bucla începe de la 2 tocmai pentru că 0 și 1 NU sunt prime. Nu le include în rezultat.

Greșeala 3 — i <= N în loc de i*i <= N la bucla exterioară: nu dă rezultat greșit, dar pierzi optimizarea — bucla merge inutil până la N.

Greșeala 4 — N prea mare pentru un vector local: un bool compus[N+1] cu N de ordinul milioanelor trebuie declarat global, nu în main (stiva e prea mică, dă crash).

Recapitulare

Ciurul găsește toate primele până la n tăind multiplii fiecărui prim, în loc să verifice numerele unul câte unul.
Pornești marcarea de la i·i și oprești bucla exterioară la √n — ambele optimizări se bazează pe faptul că factorii mici au tăiat deja restul.
Rulează în O(n log log n) timp și O(n) spațiu; vectorul mare se declară global.