Verificarea unui număr prim în C++: de la naiv la eficient

Un număr natural este prim dacă are exact doi divizori: 1 și pe el însuși. Primele numere prime sunt 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Din definiție rezultă imediat două cazuri pe care mulți le uită: 0 și 1 nu sunt prime (0 are o infinitate de divizori, 1 are unul singur), iar 2 este singurul număr prim par.

La BAC informatică, verificarea primalității apare ca subprogram cerut la Subiectul III, ca parte dintr-o problemă mai mare („câte numere prime sunt în fișier”) sau ca algoritm în pseudocod pe care trebuie să-l recunoști. Hai să vedem cum se ajunge de la soluția naivă la cea eficientă.

Varianta 1: numărarea tuturor divizorilor

Traducerea directă a definiției: numeri divizorii de la 1 la n și verifici dacă sunt exact doi.

bool primNaiv(int n)
{
    int nr = 0;
    for (int d = 1; d <= n; d++)
        if (n % d == 0)
            nr++;
    return nr == 2;
}

Este corectă pentru orice n, inclusiv 0 și 1 (pentru 1 numără un divizor, pentru 0 bucla nu se execută). Problema este timpul: pentru n = 1 000 000 007 face un miliard de împărțiri. La Subiectul III, unde se cere explicit eficiență, nu primești punctajul de eficiență cu o asemenea soluție.

Varianta 2: căutarea unui divizor propriu

Nu e nevoie să numeri toți divizorii. E suficient să găsești unul singur între 2 și n−1: dacă există, numărul nu e prim și te poți opri.

bool prim2(int n)
{
    if (n < 2)
        return false;
    for (int d = 2; d < n; d++)
        if (n % d == 0)
            return false;
    return true;
}

Pentru numerele compuse se oprește repede, dar pentru un număr prim mare face tot aproximativ n pași.

Varianta eficientă: de ce te oprești la radical din n

Divizorii unui număr vin în perechi: dacă d divide n, atunci și n / d divide n. De exemplu, pentru 36 perechile sunt (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). În fiecare pereche, unul dintre numere este cel mult √n, iar celălalt cel puțin √n. Prin urmare, dacă n are un divizor propriu, are sigur unul care este cel mult √n. Dacă nu găsești niciun divizor până la √n, nu există nici după.

bool prim(int n)
{
    if (n < 2)
        return false;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0)
            return false;
    return true;
}

Condiția d * d <= n este echivalentă cu d <= √n, dar lucrează doar cu întregi, deci nu ai erori de rotunjire și nu ai nevoie de <cmath>. Pentru un număr de ordinul 10⁹, bucla face cel mult aproximativ 31 623 de pași, față de un miliard. Asta înseamnă complexitate O(√n).

Verifică funcția pe cazurile-limită: pentru 2 și 3, condiția d * d <= n e falsă din prima (4 > 3), deci se întoarce true — corect. Pentru 4, d = 2 găsește divizorul. Pentru 25, bucla ajunge la d = 5 (25 ≤ 25) și găsește divizorul. Dacă ai fi scris d * d < n, 25 ar fi fost declarat prim — greșeală clasică.

O optimizare în plus: doar divizori impari

După ce ai tratat separat numerele pare, poți testa doar divizori impari, ceea ce înjumătățește numărul de pași:

bool primRapid(int n)
{
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int d = 3; d * d <= n; d = d + 2)
        if (n % d == 0)
            return false;
    return true;
}

Complexitatea rămâne O(√n); la BAC ambele variante sunt considerate eficiente. Alege-o pe cea pe care o scrii fără greșeli.

Capcane frecvente

• Uitarea cazurilor 0 și 1. Fără if (n < 2), funcția eficientă întoarce true pentru 0 și 1.
• Numere care „par” prime. 91 = 7 · 13, 51 = 3 · 17, 87 = 3 · 29, 57 = 3 · 19. La grile, verifică, nu ghici.
• Variabila-contor folosită după buclă. Dacă scrii varianta cu break și verifici apoi d, ai grijă ce valoare are d la ieșire în ambele situații.
• Depășirea la d * d. Pentru valori foarte aproape de limita lui int, produsul poate depăși. Dacă n poate fi atât de mare, scrie condiția ca d <= n / d.

Aplicație: câte numere prime sunt într-un fișier

Fișierul numere.in conține numere naturale de cel mult 9 cifre. Programul afișează câte dintre ele sunt prime:

#include <fstream>
using namespace std;

bool prim(int n)
{
    if (n < 2)
        return false;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0)
            return false;
    return true;
}

int main()
{
    ifstream fin("numere.in");
    ofstream fout("numere.out");
    int x, nr = 0;
    while (fin >> x)
        if (prim(x))
            nr++;
    fout << nr;
    return 0;
}

Pentru fișierul 1 2 9 13 91 97 100 se scrie 3 (numerele prime sunt 2, 13 și 97). Dacă însă fișierul are foarte multe numere, toate mici (de exemplu, până la 10⁶), o soluție mai bună este să precalculezi toate numerele prime cu ciurul lui Eratostene și să răspunzi pentru fiecare număr într-un singur pas.