Ciurul lui Eratostene

De ce contează?

Imaginează-ți numerele de la 2 la N scrise pe tablă. Tai toți multiplii lui 2 (în afară de 2), apoi toți multiplii lui 3, apoi ai lui 5... Numerele care scapă netăiate sunt exact cele prime. Eratostene a inventat această „sită" acum peste 2000 de ani.

Ideea: elimini compușii, rămân primele

Testul de primalitate verifică un număr. Dar dacă vrei toate primele până la N, e risipă să-l aplici de N ori. Ciurul calculează toate primele deodată: pleci de la presupunerea că toate sunt prime și „tai" multiplii fiecărui prim găsit.

Algoritm pas cu pas (N = 16)

Toate numerele 2..16 sunt presupuse prime.
2 e prim → taie 4, 6, 8, 10, 12, 14, 16.
3 e prim → taie 9, 15 (6, 12 deja tăiate).
5: 5·5 = 25 > 16 → ne oprim.

Rămân netăiate: 2, 3, 5, 7, 11, 13.

stare	P	P	C	P	C	P	C	C	C	P	C	P	C	C
nr	2	3	4	5	6	7	8	9	10	11	12	13	14	15

P = prim (nemarcat), C = compus (marcat). Numerele evidențiate sunt cele rămase prime după ce ai tăiat toți multiplii.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    bool compus[1000001] = {false};     // false = posibil prim

    for (int i = 2; (long long)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 << " ";   // ce a ramas e prim
    }
    return 0;
}

Observația-cheie

Pornim marcarea de la i·i, nu de la 2·i. Multiplii mai mici (2i, 3i, ...) au deja un factor prim mai mic care i-a tăiat. E optimizarea care face Ciurul rapid.

De ce e atât de eficient

A testa fiecare număr până la N individual costă O(N·√N). Ciurul marchează fiecare compus de puține ori în total, ajungând la O(N log log N) — practic liniar. E tehnica standard de precalculare când ai nevoie de multe interogări despre primalitate.

Complexitate

Metodă	Timp	Spațiu
Ciur	O(N log log N)	O(N)
test individual × N	O(N·√N)	O(1)

Greșeli frecvente

Capcane reale la Ciur:

Pornești marcarea de la 2*i: corect, dar mai lent (muncă dublă). Pornește de la i*i.
Overflow la i*i: pentru N mare, i*i se sparge în int. Scrie (long long)i * i.
Tratezi 0 și 1 ca prime: bucla pornește de la 2, dar nu uita că 0 și 1 NU sunt prime.
Memorie pentru N uriaș: un bool[N] pentru N = 10⁹ nu încape. Ciurul e pentru N până la ~10⁷–10⁸.

Vizualizare

Urmărește cum, pentru fiecare prim găsit, se taie pe rând toți multiplii lui, iar numerele rămase nemarcate se conturează ca prime:

Indiciu

Observă că multiplii lui 2 se taie primii, apoi cei ai lui 3 — unii erau deja tăiați. De-aici pornirea de la i·i: ce e mai mic a fost deja marcat.

De reținut

Ciurul găsește toate primele până la N deodată, tăind multiplii fiecărui prim.
Marcarea pornește de la i·i (cu (long long)i*i la N mare); ce rămâne nemarcat e prim.
O(N log log N), aproape liniar — tehnică de precalculare pentru multe interogări.