Numere prime

Testul de primalitate corect, cazurile limită care se uită mereu și cum îl folosești în probleme mai mari.

Definiția, exact

Un număr natural este prim dacă are exact doi divizori: 1 și el însuși.

Din definiție rezultă câteva lucruri pe care trebuie să le reții ca atare:

• 1 nu este prim, pentru că are un singur divizor.
• 0 nu este prim, pentru că are o infinitate de divizori.
• 2 este prim și este singurul număr prim par.
• Numerele negative nu se discută ca prime.

Din cauza lui 0 și 1 pică multe programe altfel corecte. Verifică-le mereu.

Testul

Un număr este prim dacă nu are niciun divizor între 2 și √n. Poate pare firesc să mergi până la n-1. Imediat după cod vezi de ce e destul să te oprești la √n. Citește explicația, pentru că ea arată că testul este corect, nu doar rapid.

bool esteprim(int n) {
    if (n < 2) return false;        // 0 și 1
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0)
            return false;
    return true;
}

Pentru n = 2 bucla nu pornește (2·2 > 2), deci funcția întoarce true. Răspunsul e corect fără niciun caz special.

Pentru n = 1 intervine prima linie.

Forma aceasta merită s-o știi pe de rost.

De ce e destul să mergi până la √n

Mulți elevi memorează regula fără s-o înțeleagă, deși argumentul are trei rânduri.

Presupune că n nu este prim. Atunci se scrie ca produs a doi factori, amândoi mai mari decât 1:

n = a · b,   cu 1 < a ≤ b < n

L-am notat cu a pe cel mai mic dintre cei doi.

Cât de mare poate fi a? Dacă am avea a > √n, atunci și b ≥ a > √n, iar produsul lor ar fi

a · b > √n · √n = n

adică n > n, ceea ce e imposibil. Rămâne că a ≤ √n.

Am arătat astfel că orice număr compus are cel puțin un divizor între 2 și √n.

Citit invers, asta e exact ce ne trebuie. Dacă am încercat toate numerele de la 2 la √n și niciunul nu divide pe n, atunci n nu poate fi compus, deci este prim. Nu are rost să căutăm dincolo de √n: orice divizor mai mare de atât vine obligatoriu în pereche cu unul mai mic, pe care l-am fi găsit deja.

Argumentul nu spune „probabil nu mai găsim nimic". Spune că acolo nu poate exista nimic. E o demonstrație, iar oprirea la √n nu e o optimizare riscantă.

Pe un exemplu

91 = 7 · 13, iar √91 ≈ 9,54. Factorul mic, 7, este într-adevăr sub 9,54. Îl găsim la d = 7 și ne oprim, fără să ajungem vreodată la 13.

Perechile de divizori ai lui 100 arată de ce √n este exact punctul de cotitură:

Coloana din stânga crește, cea din dreapta scade, iar cele două se întâlnesc fix la 10 = √100. După acest punct ar urma aceleași perechi, citite invers.

De ce d d <= n, și nu d d < n

Semnul ≤ nu e pus din neatenție. Când cei doi factori sunt egali, amândoi sunt exact √n, iar singurul divizor al numărului se află chiar în capătul intervalului. Dacă oprești bucla înainte de el, nu îl mai vezi.

Pentru n = 49, cu d d <= n ajungem la d = 7, testăm 49 % 7, găsim restul 0 și răspundem corect că nu este prim. Cu d d < n, bucla s-ar opri chiar înainte de d = 7, iar 49 ar fi declarat prim.

Greșeala apare rar. Până la 200, cele două variante diferă doar la 4, 9, 25, 49, 121 și 169, adică la pătratele numerelor prime. La un pătrat ca 36 nu se întâmplă nimic, pentru că 2 îl divide și e găsit cu mult înainte de 6. Numai la p² cel mai mic divizor stă chiar la √n.

Tocmai de aceea trece ușor de o testare superficială: sunt doar șase valori greșite din primele două sute și niciuna nu pare suspectă.

Aceeași idee, cu indicator

Dacă nu ai voie să folosești return din mijlocul funcției, sau dacă scrii în pseudocod:

int d = 2;
bool prim = (n >= 2);
while (d * d <= n && prim) {
    if (n % d == 0) prim = false;
    d++;
}

citește n
p ← 1
┌dacă n < 2 atunci
│ p ← 0
└■
d ← 2
┌cât timp d*d <= n și p = 1 execută
│ ┌dacă n % d = 0 atunci
│ │ p ← 0
│ └■
│ d ← d + 1
└■
scrie p

Optimizarea cu pas 2

Dacă n nu se divide cu 2, atunci nu se divide cu niciun număr par. Poți deci să testezi separat 2 și apoi doar numerele impare:

bool esteprim(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 += 2)
        if (n % d == 0)
            return false;
    return true;
}

Numărul de pași scade la jumătate. Merită dacă testezi multe numere. Pentru unul singur, diferența nu se simte.

Unde apare la examen

Rar ți se cere doar „este prim". De obicei testul e o piesă dintr-o problemă mai mare.

Câte numere prime sunt într-un interval

int cate = 0;
for (int x = a; x <= b; x++)
    if (esteprim(x))
        cate++;

Cel mai mare număr prim mai mic decât n

int x = n - 1;
while (x >= 2 && !esteprim(x))
    x--;

Numere gemene

Sunt două numere prime care diferă prin 2: (3,5), (5,7), (11,13), (17,19).

for (int x = 2; x + 2 <= n; x++)
    if (esteprim(x) && esteprim(x + 2))
        cout << x << " " << x + 2 << "\n";

Costul

Testul face √n pași. Dacă îl aplici fiecărui număr până la n, ajungi în total la aproximativ n · √n pași. Pentru n = 10⁶ sunt cam un miliard, adică prea mulți.

Când ai nevoie de toate numerele prime până la o limită, testul individual nu mai e metoda potrivită. Există algoritmi care le găsesc pe toate deodată, mult mai repede. În problemele obișnuite de la bac testezi câteva numere sau parcurgi un interval mic, iar acolo forma de mai sus e exact ce trebuie.

O greșeală frecventă

for (int d = 2; d <= n / 2; d++)     // merge, dar e lent
for (int d = 2; d < n; d++)          // și mai lent

Ambele sunt corecte matematic. Prima face n/2 pași, a doua n. Varianta cu d * d <= n face √n. Pentru n = 10⁹ înseamnă 500 de milioane, un miliard, respectiv 31.623 de pași.

La bac se punctează și eficiența, așa că alegerea dintre ele poate face diferența între punctajul complet și unul parțial.

De reținut

• Prim înseamnă exact doi divizori. 0 și 1 nu sunt prime, 2 este.
• Testează divizori doar până la √n, cu d * d <= n.
• Motivul nu este că „probabil nu mai găsim nimic". Orice număr compus are un divizor sub √n, altfel produsul celor doi factori ar depăși pe n.
• Pune ≤ în condiție, nu <. Altfel pătratele numerelor prime (4, 9, 25, 49…) sunt declarate prime.
• Tratează n < 2 înainte de buclă. Restul cazurilor merg de la sine.
• Testul individual costă √n. Aplicat pe tot intervalul, devine scump.