Ciurul lui Eratostene: toate numerele prime până la n

Ciurul lui Eratostene este un algoritm care determină toate numerele prime mai mici sau egale cu un n dat. În loc să verifice fiecare număr separat, pornește de la presupunerea că toate sunt prime și „taie” multiplii fiecărui număr prim găsit. Ce rămâne netăiat este prim. La BAC informatică este un instrument foarte bun pentru problema de eficiență de la Subiectul III, atunci când datele sunt multe și mărginite.

Ideea ciurului lui Eratostene, pe hârtie

Să luăm n = 30. Scriem numerele de la 2 la 30 și procedăm astfel:

1. Primul număr netăiat este 2, deci e prim. Tăiem multiplii lui: 4, 6, 8, …, 30.
2. Următorul număr netăiat este 3, prim. Tăiem multiplii lui începând cu 9: 9, 12, 15, 18, 21, 24, 27, 30 (unii erau deja tăiați).
3. 4 este tăiat, îl sărim.
4. 5 este netăiat, prim. Tăiem multiplii de la 25: 25, 30.
5. Următorul candidat ar fi 6, dar 6 · 6 = 36 > 30, așa că ne oprim.

Au rămas netăiate: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — cele 10 numere prime până la 30.

Două observații fac algoritmul rapid. Prima: tăierea multiplilor lui i poate începe de la i · i, pentru că multiplii mai mici (2i, 3i, …) au un factor mai mic decât i și au fost deja tăiați. A doua: e suficient ca i să meargă până la √n; după aceea nu mai e nimic de tăiat.

Implementarea în C++

Folosim un vector în care ciur[x] este 0 dacă x este (încă) considerat prim și 1 dacă a fost tăiat. Un vector global este inițializat automat cu zero, ceea ce ne scutește de o buclă.

#include <iostream>
using namespace std;

const int NMAX = 1000000;
bool ciur[NMAX + 1];     // global: toate elementele sunt false (0)

int main()
{
    int n;
    cin >> n;            // n <= 1000000, de exemplu 30
    ciur[0] = ciur[1] = true;            // 0 și 1 nu sunt prime
    for (int i = 2; i * i <= n; i++)
        if (!ciur[i])                    // i este prim
            for (int j = i * i; j <= n; j = j + i)
                ciur[j] = true;          // tăiem multiplii lui i
    for (int x = 2; x <= n; x++)
        if (!ciur[x])
            cout << x << " ";
    return 0;
}

Pentru n = 30 se afișează 2 3 5 7 11 13 17 19 23 29. Atenție la convenție: aici true înseamnă „tăiat”, adică neprim. Poți folosi și convenția inversă, dar alege una și respect-o în tot programul; amestecul lor este o greșeală frecventă.

De ce este ciurul rapid

Pentru fiecare număr prim i, bucla interioară face aproximativ n / i pași. Suma n/2 + n/3 + n/5 + n/7 + … crește foarte încet; complexitatea ciurului este O(n log log n), practic aproape liniară. Pentru n = 10⁶, ciurul face câteva milioane de operații simple și rulează instantaneu.

Compară cu alternativa: dacă ai de verificat 10⁶ numere, fiecare de până la 10⁶, cu funcția de primalitate în O(√n), faci până la 10⁶ · 1000 = 10⁹ operații în cazul cel mai defavorabil. Cu ciurul, construiești tabelul o dată, apoi răspunzi pentru fiecare număr cu o singură accesare: ciur[x].

Cât consumă memorie

Ciurul are nevoie de un element pentru fiecare valoare de la 0 la n. Cu bool sau char, fiecare element ocupă un octet, deci pentru n = 10⁶ ai aproximativ 1 MB, iar pentru 10⁷ aproximativ 10 MB. Cu int ai folosi de patru ori mai mult, fără niciun câștig. Declară vectorul global: un tablou mare declarat local, în main, poate depăși memoria rezervată pentru variabilele locale și programul se poate opri la rulare.

Limita practică: ciurul merge doar dacă valorile sunt mărginite de o constantă rezonabilă (de ordinul 10⁶–10⁷). Pentru un singur număr de ordinul 10⁹, verificarea directă până la √n este alegerea corectă.

Când merită să folosești ciurul la BAC

• Ai multe numere de verificat (sute de mii, un milion) și toate sunt mici (de exemplu, cel mult 10⁶).
• Trebuie să afișezi sau să numeri toate numerele prime dintr-un interval [a, b] cu b mărginit.
• Ai nevoie de numere prime în mod repetat în același program (de exemplu, pentru descompuneri sau pentru „cel mai mic număr prim mai mare decât x”).

Dacă ai un singur număr sau câteva, ciurul este o complicație inutilă: funcția de primalitate cu d * d <= n este suficientă.

Problemă de eficiență: numere prime dintr-un fișier

Fișierul bac.in conține cel mult 10⁶ numere naturale din intervalul [0, 10⁶]. Se cere să se scrie în bac.out câte dintre ele sunt prime.

Descrierea algoritmului: construiesc o singură dată ciurul lui Eratostene pentru valorile până la 10⁶, într-un vector global de tip bool. Apoi citesc numerele din fișier unul câte unul, fără să le memorez, și pentru fiecare verific în O(1) dacă este marcat ca prim, numărând aparițiile. Timpul este dat de construirea ciurului, aproape liniară în valoarea maximă, plus o operație pentru fiecare număr citit; memoria este de un octet pentru fiecare valoare posibilă, independent de numărul de date.

#include <fstream>
using namespace std;

const int VMAX = 1000000;
bool neprim[VMAX + 1];

int main()
{
    ifstream fin("bac.in");
    ofstream fout("bac.out");
    neprim[0] = neprim[1] = true;
    for (int i = 2; i * i <= VMAX; i++)
        if (!neprim[i])
            for (int j = i * i; j <= VMAX; j = j + i)
                neprim[j] = true;
    int x, nr = 0;
    while (fin >> x)
        if (!neprim[x])
            nr++;
    fout << nr;
    return 0;
}

Pentru fișierul 0 1 2 9 13 91 97 100 999983 se scrie 4: sunt prime 2, 13, 97 și 999983 (cel mai mare număr prim mai mic decât un milion).