Ciurul lui Eratostene

Ciurul lui Eratostene află toate numerele prime până la o limită dată. Pornim cu numerele de la 2 la $N$ și eliminăm multiplii fiecărui număr rămas. Pentru $N=10$, eliminăm 4, 6, 8, 10 ca multipli de 2, apoi 9 ca multiplu de 3; rămân 2, 3, 5, 7.

Ciurul lui Eratostene construiește, pentru o limită $N$ dată, un tablou de valori logice prim[0..N]: prim[i] este adevărat dacă $i$ este număr prim. Tabloul pornește cu toate valorile adevărate, apoi se marchează 0 și 1 ca neprime. Pentru fiecare $p\ge 2$ rămas marcat prim și cu $p\cdot p\le N$ se marchează ca neprime multiplii lui $p$, începând cu $p^2$: multiplii mai mici de forma $p\cdot k$, cu $k<p$, au fost deja marcați când s-a prelucrat un factor prim al lui $k$. Prelucrarea se oprește la $p\cdot p>N$, pentru că orice număr compus $\le N$ are un divizor prim cel mult $\sqrt{N}$. Timpul este proporțional cu $N\log \log N$, iar memoria este proporțională cu $N$.

Exemplul 1 — numerele prime până la 30. Se prelucrează valorile $p$ cu $p\cdot p\le 30$, adică 2, 3 și 5.

1. $p=2$: se marchează 4, 6, 8, ..., 30, în total 14 numere.
2. $p=3$: se marchează 9, 12, 15, ..., 30, în total 8 numere, dintre care 12, 18, 24 și 30 fuseseră marcate de 2.
3. $p=4$ este deja marcat și se sare peste el.
4. $p=5$: se marchează 25 și 30, în total 2 numere; 30 era deja marcat.
5. $p=6$ are $6\cdot 6=36>30$, deci prelucrarea se oprește.

Rămân nemarcate 2, 3, 5, 7, 11, 13, 17, 19, 23 și 29: zece numere prime. În total s-au făcut $14+8+2=24$ de marcări pentru cele 19 numere compuse de până la 30, deci cinci marcări au căzut pe numere deja marcate.

N = 30
prim = [True] * (N + 1)
prim[0] = prim[1] = False
p = 2
while p * p <= N:
    if prim[p]:
        for m in range(p * p, N + 1, p):
            prim[m] = False
    p += 1
print([i for i in range(2, N + 1) if prim[i]])

Exemplul 2 — numărul și cel mai mare număr prim până la 100. Aceeași metodă, scrisă în C++, numără valorile rămase adevărate:

#include <iostream>
using namespace std;
int main() {
    const int N = 100;
    bool prim[N + 1];
    for (int i = 0; i <= N; ++i) prim[i] = true;
    prim[0] = prim[1] = false;
    for (int p = 2; p * p <= N; ++p)
        if (prim[p])
            for (int m = p * p; m <= N; m += p)
                prim[m] = false;
    int nr = 0, ultim = 0;
    for (int i = 2; i <= N; ++i)
        if (prim[i]) { nr++; ultim = i; }
    cout << nr << ' ' << ultim;
    return 0;
}

Programul afișează 25 97: între 1 și 100 sunt 25 de numere prime, iar cel mai mare este 97. După construirea ciurului, întrebarea „este $i$ prim?” se rezolvă printr-o singură citire din tablou, în timp constant, ceea ce îl face potrivit atunci când trebuie testate multe numere de la 1 la $N$.

Ideea ciurului. Scrii numerele de la 2 la $N$. Primul număr nemarcat, 2, e prim; îi marchezi toți multiplii mai mari. Următorul nemarcat, 3, e prim; îi marchezi multiplii. Continui așa: fiecare număr care a rămas nemarcat până când ajungi la el nu are niciun divizor prim mai mic decât el, deci este prim. Bucla exterioară se oprește la $i\cdot i\le N$, pentru că dacă $i\cdot i>N$ numărul $i$ nu mai are multipli de marcat.

Testul pentru un singur număr. Un număr natural $n$ este prim dacă are exact doi divizori, pe 1 și pe $n$. Deci 0 și 1 nu sunt prime, iar 2 este singurul număr prim par. Încerci divizorii $d=2,3,4,\dots$ cât timp $d\cdot d\le n$; dacă găsești unul, $n$ nu e prim. În cod, condiția $d\cdot d\le n$ se scrie d <= n / d: evită calculul radicalului și erorile de rotunjire ale lui sqrt, iar pentru $n$ apropiat de valoarea maximă a tipului int (2147483647) nu calculează produsul d * d, care ar putea depăși tipul. Pentru numere întregi pozitive, cele două condiții sunt echivalente.

int prim(int n) {
    if (n < 2)
        return 0;
    for (int d = 2; d <= n / d; d++)
        if (n % d == 0)
            return 0;
    return 1;
}

Pentru 997 se încearcă divizorii de la 2 la 31 ($32\cdot 32=1024>997$) și niciunul nu se potrivește: 997 este prim. Pentru $1001=7\cdot 11\cdot 13$, testul se oprește la $d=7$.

În varianta C++ cu tablou c, convenția este: c[k] = 0 înseamnă „$k$ este prim”, c[k] = 1 înseamnă „$k$ nu este prim”, iar c[0] = c[1] = 1. Pentru fiecare $i$ cu $i\cdot i\le N$ și c[i] == 0, marchezi c[j] = 1 pentru $j=i\cdot i,i\cdot i+i,\dots$, până la $N$.

Cât de rapid este. Pentru $N=1000000$, ciurul face 2 122 048 de marcări, iar după aceea răspunsul la întrebarea „$k$ este prim?” este o singură citire, c[k]. Numărul de marcări crește aproape proporțional cu $N$ (ordinul $N\log \log N$). Testarea separată a fiecărui număr până la $N$ cu divizori până la $\sqrt{n}$ poate cere, în cel mai rău caz, de ordinul $N\sqrt{N}$ împărțiri. Prețul ciurului este memoria: un tablou cu $N+1$ elemente, care pentru $N=1000000$ înseamnă aproximativ un megaoctet dacă elementele sunt de tip char sau bool.

Exemple suplimentare

Exemplul 3 — urmărirea pentru $N=100$ și cazuri-limită. Se prelucrează $p=2,3,5,7$, pentru că $7\cdot 7=49\le 100$, iar $11\cdot 11=121>100$. Numărul de marcări este 49 pentru $p=2$ (de la 4 la 100), 31 pentru $p=3$ (de la 9 la 99), 16 pentru $p=5$ (de la 25 la 100) și 8 pentru $p=7$ (de la 49 la 98): în total $49+31+16+8=104$ marcări. Doar 74 dintre ele cad pe numere încă nemarcate, deoarece între 2 și 100 sunt $99-25=74$ de numere compuse; restul sunt remarcări. Pentru $p=7$, marcarea începe de la 49, nu de la 14: numerele 14, 21, 28, 35 și 42 sunt multipli ai lui 2, 3 sau 5, deci au fost marcate mai devreme. Pentru $N=2$ ciclul exterior nu se execută deloc ($2\cdot 2>2$), iar rezultatul corect este singurul prim 2. Pentru $N=1$ nu rămâne niciun prim.

Exemple rezolvate

Exemplul 1: ciurul până la 30, pas cu pas.

1. $i=2$ (nemarcat, prim): marchezi 4, 6, 8, …, 30.
2. $i=3$ (nemarcat, prim): marchezi 9, 12, 15, 18, 21, 24, 27, 30; unele erau deja marcate.
3. $i=4$ este marcat, deci nu faci nimic.
4. $i=5$ (nemarcat, prim): marchezi 25 și 30.
5. $i=6$: $6\cdot 6=36>30$, bucla se oprește.
6. Rămân nemarcate: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, adică 10 numere prime.

#include <iostream>
using namespace std;

char c[31];

int main() {
    int N = 30;
    c[0] = c[1] = 1;
    for (int i = 2; i * i <= N; i++)
        if (c[i] == 0)
            for (int j = i * i; j <= N; j = j + i)
                c[j] = 1;                // j are divizorul i, deci nu e prim
    for (int k = 2; k <= N; k++)
        if (c[k] == 0)
            cout << k << " ";
    cout << "\n";
    return 0;
}

Programul afișează:

2 3 5 7 11 13 17 19 23 29

Tabloul c este global, deci toate elementele lui pornesc de la 0.

Exemplul 2: câte numere prime sunt până la $N$. Se citește $N\le 1000000$. Afișează câte numere prime sunt cel mult egale cu $N$.

#include <iostream>
using namespace std;

char c[1000001];

int main() {
    int N;
    cin >> N;
    c[0] = c[1] = 1;
    for (int i = 2; i * i <= N; i++)
        if (c[i] == 0)
            for (int j = i * i; j <= N; j = j + i)
                c[j] = 1;
    int nr = 0;
    for (int k = 2; k <= N; k++)
        if (c[k] == 0)
            nr++;
    cout << nr << "\n";
    return 0;
}

Pentru intrarea 1000000, programul afișează:

78498

Pentru 100 afișează 25, iar pentru 30 afișează 10, ca în exemplul 1.

Exemplul 3: un singur număr. Verifică dacă 997 și 1001 sunt prime, cu subprogramul prim de mai sus.

1. 997: niciun divizor de la 2 la 31, deci este prim.
2. 1001: se împarte la 7, deci nu este prim. Pentru un singur număr nu are rost să construiești ciurul până la 1001.

#include <iostream>
using namespace std;

int prim(int n) {
    if (n < 2)
        return 0;
    for (int d = 2; d <= n / d; d++)
        if (n % d == 0)
            return 0;
    return 1;
}

int main() {
    int n;
    cin >> n;
    cout << prim(n) << "\n";
    return 0;
}

Pentru intrarea 997, programul afișează:

1

Pentru 1001 afișează 0.

Exemplul 4: numere prime gemene. Două numere prime gemene sunt două numere prime care diferă prin 2, de exemplu 11 și 13. Câte perechi de numere prime gemene au ambele numere cel mult egale cu 100?

1. Construiești ciurul până la 100.
2. Pentru fiecare $p$ de la 2 la 98, verifici dacă c[p] == 0 și c[p + 2] == 0.
3. Perechile sunt (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73): 8 perechi.

#include <iostream>
using namespace std;

char c[101];

int main() {
    int N = 100, nr = 0;
    c[0] = c[1] = 1;
    for (int i = 2; i * i <= N; i++)
        if (c[i] == 0)
            for (int j = i * i; j <= N; j = j + i)
                c[j] = 1;
    for (int p = 2; p + 2 <= N; p++)
        if (c[p] == 0 && c[p + 2] == 0) {
            cout << "(" << p << "," << p + 2 << ") ";
            nr++;
        }
    cout << "\n" << nr << "\n";
    return 0;
}

Programul afișează:

(3,5) (5,7) (11,13) (17,19) (29,31) (41,43) (59,61) (71,73)
8

Exemplul 5: nivel de examen, multe întrebări. Se citesc $n$ și apoi $n$ numere naturale, fiecare cel mult 1 000 000. Afișează câte dintre ele sunt prime, cu un algoritm eficient din punctul de vedere al timpului de executare.

1. Construiești o singură dată ciurul până la 1 000 000.
2. Pentru fiecare număr citit, răspunsul este c[x] == 0, o singură operație, oricât de mare ar fi $n$.
3. Pentru numerele 2, 15, 97, 1, 999983, 1000000 răspunsul este 3: 2, 97 și 999983 (cel mai mare număr prim mai mic decât un milion).

#include <iostream>
using namespace std;

char c[1000001];

int main() {
    const int N = 1000000;
    c[0] = c[1] = 1;
    for (int i = 2; i * i <= N; i++)
        if (c[i] == 0)
            for (int j = i * i; j <= N; j = j + i)
                c[j] = 1;
    int n, x, nr = 0;
    cin >> n;
    for (int k = 1; k <= n; k++) {
        cin >> x;
        if (c[x] == 0)
            nr++;
    }
    cout << nr << "\n";
    return 0;
}

Pentru intrarea 6 urmată de 2 15 97 1 999983 1000000, programul afișează:

3

Dacă ai testa fiecare număr cu divizori până la $\sqrt{x}$, ai face până la 1 000 de împărțiri pentru fiecare număr citit; cu ciurul, timpul de după construcție nu mai depinde de mărimea numerelor.

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen cuprinde „Divizibilitate. Numere prime. Algoritmul lui Euclid”, la algoritmii elementari, și „Analiza complexității unui algoritm”; ciurul lui Eratostene nu este numit, dar este metoda obișnuită când se cere un algoritm eficient pentru multe numere până la aceeași limită (anexa 2 la OMECTS 4800/2010). Formatul probei și subiectele din 2026 sunt pe pagina subiectelor și baremelor Bac 2026.

Testarea primalității este la clasa a IX-a pe programa veche (OMECI 5099/2009), iar tablourile, de care are nevoie ciurul, la clasa a X-a. Pe programa nouă de clasa a IX-a apar parcurgerea divizorilor, descompunerea în factori primi și listele (OMEC 6930/2025, anexa 42).

Greșeli frecvente

• Greșit: 0 și 1 rămân marcate ca prime.
  Corect: ambele se marchează neprime la început; în ciur, c[0] și c[1] se marchează separat, iar testul începe cu if (n < 2) return 0;.
• Greșit: se șterge și p când procesăm multiplii lui p.
  Corect: marcarea începe de la $p^2$ (sau de la $2p$), niciodată de la $p$; altfel toate numerele prime ar fi marcate ca neprime.
• Greșit: după ciur trebuie retestat fiecare număr prin împărțiri.
  Corect: marcajele conțin deja răspunsul pentru interval.
• Greșit: condiția testului este d * d < n.
  Corect: cu d * d < n, pătratele de numere prime, ca 49, ar fi declarate prime; condiția corectă include egalitatea.
• Greșit: pentru $N=1000000$ un tablou cu 1 000 000 de elemente este suficient.
  Corect: tabloul are nevoie de 1 000 001 elemente, ca să existe c[1000000].
• Greșit: un tablou de un milion de elemente poate fi declarat local în main.
  Corect: poate depăși memoria rezervată variabilelor locale; declarat global, ca în exemple, este și inițializat automat cu 0.

Înainte și după

Întrebări frecvente