Ciurul lui Eratostene: numere prime până la n

Ciurul lui Eratostene determină toate numerele prime până la o limită n. Pornești cu toate numerele de la 2 considerate candidate și elimini multiplii fiecărui prim. Rezultatul este un tabel reutilizabil, nu doar răspunsul pentru un singur număr.

Alegerea față de testarea prin împărțitori depinde de cerință. Pentru o întrebare izolată despre un număr mare, tabelul poate costa prea mult. Pentru mii de întrebări în același interval, precalcularea este adesea mult mai potrivită.

Cum funcționează

Inițializăm marcajele și eliminăm explicit zero și unu. Pentru fiecare p încă marcat prim, eliminăm pp, pp+p și ceilalți multipli. Începem la pătrat deoarece multiplii mai mici au deja un factor prim mai mic decât p și au fost tratați.

Nu trebuie să pornim eliminări de la fiecare număr compus. Dacă p nu este prim, multiplii săi au fost deja afectați de un factor prim al lui p. Bucla exterioară se poate opri la rădăcina lui n: orice compus până la n are cel puțin un factor prim care nu depășește această rădăcină.

Programul presupune 2 <= n <= 100000. Tabloul clasic rezervă 100001 poziții. Varianta cu std::vector folosește aici vector, cu zero și unu ca marcaje, pentru a evita particularitățile specializării vector. Semnificația algoritmică este identică: fiecare indice reprezintă numărul verificat.

Exemplu urmărit pas cu pas

Pentru n=20, p=2 elimină 4,6,8,10,12,14,16,18,20. p=3 elimină 9,12,15,18. Numărul 4 este deja compus, iar următorul prim 5 are pătratul peste 20. Rămân 2,3,5,7,11,13,17,19.

Observă că 12 și 18 pot fi marcate de mai multe ori. Nu este o eroare: atribuirea false este idempotentă. Dacă am vrea numărul factorilor sau cel mai mic factor prim, am schimba informația memorată și regula de actualizare, nu am interpreta simplul marcaj ca pe un contor.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n;
    std::cin >> n;
    bool prim[100001];
    for (int i = 0; i <= n; ++i)
        prim[i] = true;
    prim[0] = prim[1] = false;
    for (int p = 2; p <= n / p; ++p)
        if (prim[p])
            for (int j = p * p; j <= n; j += p)
                prim[j] = false;
    bool first = true;
    for (int i = 2; i <= n; ++i)
        if (prim[i]) {
            if (!first)
                std::cout << ' ';
            std::cout << i;
            first = false;
        }
    std::cout << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<char> prim(n + 1);
    for (int i = 0; i <= n; ++i)
        prim[i] = true;
    prim[0] = prim[1] = false;
    for (int p = 2; p <= n / p; ++p)
        if (prim[p])
            for (int j = p * p; j <= n; j += p)
                prim[j] = false;
    bool first = true;
    for (int i = 2; i <= n; ++i)
        if (prim[i]) {
            if (!first)
                std::cout << ' ';
            std::cout << i;
            first = false;
        }
    std::cout << '\n';
}

De ce funcționează și cât costă

Un prim nu este eliminat deoarece nu are un divizor propriu mai mare decât unu. Orice compus are un factor prim p cel mult egal cu rădăcina sa și este eliminat când procesăm acel factor. Cele două afirmații acoperă atât absența eliminărilor greșite, cât și eliminarea tuturor compuselor.

Timpul ciurului clasic este O(n log log n), iar memoria O(n). După construire, întrebarea dacă x este prim se rezolvă în O(1), dacă x se află în domeniul precalculat. Construirea tabelului nu este gratuită și trebuie inclusă în costul total.

Greșeli frecvente

Nu marca p însuși ca fiind compus. Nu lăsa unu considerat prim. Pentru limite mari, calculează p*p într-un tip suficient sau verifică p <= n/p înainte. Un tablou creat pentru n nu poate răspunde pentru x>n.

Exersează

Explică la ce pas este eliminat 49 și de ce nu ajunge să verificăm doar divizibilitatea cu 2,3 și 5.

Rezolvare explicată: Numărul 49 este eliminat când p=7, începând chiar de la 7². Nu se divide cu 2,3 sau 5, deci omiterea factorului 7 l-ar clasifica greșit.

Continuă să înveți

Divizibilitate, vectori și analiza costului.

Întrebări frecvente

De ce începe eliminarea de la p*p?

Multiplii mai mici ai lui p au un factor mai mic decât p și au fost deja eliminați. Pornirea de la pătrat evită o parte din munca repetată.

De ce zero și unu nu sunt prime?

Un număr prim are exact doi divizori pozitivi distincți. Unu are un singur divizor pozitiv, iar zero nu îndeplinește definiția unui număr prim.

Este ciurul potrivit pentru un singur număr foarte mare?

Nu întotdeauna. Memoria crește cu limita până la care construiești tabelul. Pentru o singură verificare poate fi mai potrivit un test de primalitate.

Pot folosi tabelul pentru mai multe întrebări?

Da. Construiești o singură dată până la maximul necesar, apoi citești marcajul fiecărui număr în timp constant, dacă respectă domeniul.

Ce diferență are vector față de vector?

Ambele pot reprezenta marcaje, dar vector este o specializare care compactează biți și are referințe speciale. vector păstrează accesul obișnuit la elemente.