Numere prime

Un număr prim este un întreg mai mare decât 1 cu exact doi divizori pozitivi: 1 și numărul însuși. Echivalent, nu are divizori proprii, adică divizori strict între 1 și $n$. 2, 3, 5 și 7 sunt prime; 1 nu este prim, iar 9 este compus deoarece $9=3\cdot 3$. Pentru testare, este suficient să cauți un divizor până la $\sqrt{n}$: dacă $n$ are un divizor mai mare, partenerul său este mai mic.

În Python, pentru 7 testezi restul împărțirii la 2 și 3; niciunul nu este zero, deci 7 este prim. Numărul 9 are rest zero la împărțirea la 3.

Un număr $n\ge 2$ este prim dacă nu are divizori proprii. Dacă $n=a\cdot b$ cu $1<a\le b<n$, atunci $a^2\le a\cdot b=n$, deci $a\le \sqrt{n}$. Un număr compus are așadar un divizor propriu mai mic sau egal cu $\sqrt{n}$ și testarea se oprește la $d\cdot d\le n$. Numerele 0 și 1 și cele negative nu sunt prime, iar 2 este singurul număr prim par.

Exemplul 1 — testul de primalitate. Pentru $n=97$ se testează $d=2,\dots ,9$, adică valorile cu $d\cdot d\le 97$: niciun $d$ nu divide 97 (resturile la 2, 3, 5 și 7 sunt 1, 1, 2 și 6), deci 97 este prim. Pentru $n=91$ primul $d$ care divide este 7, pentru că $91=7\cdot 13$; bucla se poate opri aici.

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    bool prim = n >= 2;
    for (int d = 2; prim && d <= n / d; ++d)
        if (n % d == 0)
            prim = false;
    cout << prim;
    return 0;
}

Pentru intrările 97, 91, 2 și 1 programul afișează 1, 0, 1 și 0. Pentru $n=2$ condiția d <= n / d este falsă de la început și rezultatul rămâne adevărat.

Câștigul este mare: pentru numărul prim $n=1000000007$ bucla face cel mult 31 621 de teste (valorile $d=2,\dots ,31622$), pe când o verificare a tuturor numerelor până la $n-1$ ar face aproape un miliard. Același test, aplicat fiecărui număr dintr-un interval și însoțit de un contor, numără numerele prime ale intervalului: în $[10;30]$ sunt șase, anume 11, 13, 17, 19, 23 și 29. Pentru fiecare dintre ele bucla se oprește la cel mult $d=5$, pentru că $5\cdot 5=25$ și $6\cdot 6=36$ depășește 30.

Exemplul 2 — descompunerea în factori primi. Împarți $n$ la fiecare $d$ cât timp divide, pornind de la $d=2$, și numeri câte împărțiri ai făcut: acesta este exponentul. Pentru $n=360$ se obține $360=2^3\cdot 3^2\cdot 5$.

1. $d=2$: $360\to 180\to 90\to 45$, exponent 3.
2. $d=3$: $45\to 15\to 5$, exponent 2.
3. $d=4$: 5 nu se împarte la 4; $4\cdot 4=16>5$, ciclul se oprește.
4. Rămâne $n=5>1$, deci 5 este un factor prim cu exponentul 1.

int n = 360;
for (int d = 2; d * d <= n; ++d) {
    int e = 0;
    while (n % d == 0) { n /= d; e++; }
    if (e > 0) cout << d << '^' << e << ' ';
}
if (n > 1) cout << n << "^1";

Secvența afișează 2^3 3^2 5^1. Din exponenți rezultă numărul divizorilor: $(3+1)(2+1)(1+1)=24$. Cel mai mare factor prim al lui 13195 se găsește tot așa: $13195=5\cdot 7\cdot 13\cdot 29$; după eliminarea factorilor 5, 7 și 13 rămâne $n=29>1$ și bucla se oprește, deci răspunsul este 29. Divizorii compuși nu apar niciodată ca factori, pentru că factorii mici au fost deja eliminați.

Exemplul 3 — numărul de divizori, în perechi. Divizorii unui număr $n$ vin în perechi $(d,n/d)$, iar pentru fiecare pereche este de ajuns să găsești divizorul mai mic, $d\le \sqrt{n}$. Pentru $n=36$ perechile sunt $(1,36)$, $(2,18)$, $(3,12)$ și $(4,9)$, iar valoarea $d=6$ dă $6\cdot 6=36$, deci perechea se reduce la un singur divizor. Numărul de divizori este $4\cdot 2+1=9$. Dacă pătratul perfect nu este tratat separat, divizorul 6 este numărat de două ori și se obține greșit 10.

int n = 36, k = 0;
for (int d = 1; d * d <= n; ++d)
    if (n % d == 0)
        k += (d * d == n) ? 1 : 2;
cout << k;

Secvența afișează 9. Același ciclu, pentru $n=97$, găsește doar perechea $(1,97)$ și afișează 2, adică exact cei doi divizori ai unui număr prim. Un număr are un număr impar de divizori numai dacă este pătrat perfect.

Cazuri-limită ale testului de primalitate. Pentru $n=4$ condiția d <= n / d este adevărată la $d=2$, iar $4\mathrm{mod}2=0$, deci 4 este compus. Pentru $n=3$ condiția este falsă de la început, pentru că $3/2=1$, iar 3 rămâne prim. Pentru pătratele numerelor prime, $9$ și $25$, testul se oprește tocmai la divizorul $3$, respectiv $5$.

Separă proprietatea „este prim” de operația „găsește primul divizor”. Condiția de oprire trebuie să includă egalitatea: pentru $n=49$ pragul $d\cdot d\le n$ ajunge la $d=7$ și găsește factorul; cu $d\cdot d<n$ numărul 49 ar fi declarat prim. Testarea lui 2 separat și apoi doar a numerelor impare înjumătățește munca. Nu înlocui condiția cu d <= sqrt(n) în aritmetică flotantă: pentru valori mari rotunjirea poate omite sau adăuga un candidat, pe când d * d <= n și d <= n / d lucrează numai cu întregi. Pentru a număra numerele prime dintr-un interval mare se folosește ciurul din lecția „Ciurul lui Eratostene”, nu testul separat al fiecărui număr. Complexitatea testului este proporțională cu $\sqrt{n}$. Atenție și la valorile mici: dacă lipsește verificarea $n\ge 2$, numerele 0 și 1 sunt declarate prime, pentru că bucla nu găsește niciun divizor.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int n = 84, k = 0;
for (int d = 2; d <= n; d++)
    if (n % d == 0) {
        k++;
        while (n % d == 0)
            n /= d;
    }
cout << k;

• a) 2
• b) 3
• c) 4
• d) 12

Răspunsul corect este b). Pentru $d=2$: 84 se împarte la 2 de două ori și $n=21$, $k=1$. Pentru $d=3$: 21 se împarte la 3 o dată, $n=7$, $k=2$. Valorile $d=4,5,6$ nu divid 7. Pentru $d=7$: $n=1$, $k=3$. Ciclul numără factorii primi distincți ai lui 84, adică 2, 3 și 7. Varianta d) este numărul tuturor divizorilor lui 84, $(2+1)(1+1)(1+1)=12$, iar varianta c) numără factorii cu exponenții din $2^2\cdot 3\cdot 7$ adunați (4 = 2+1+1).

Al doilea exemplu — cel mai mic divizor. Ce se afișează pentru $n=15$, respectiv pentru $n=17$?

int d = 2;
while (d * d <= n && n % d != 0)
    d++;
cout << d;

Pentru $n=15$: $2\cdot 2\le 15$ și $15\mathrm{mod}2\ne 0$, deci $d=3$; apoi $3\cdot 3\le 15$, dar $15\mathrm{mod}3=0$, iar ciclul se oprește. Se afișează 3, cel mai mic divizor mai mare decât 1. Pentru $n=17$: $d$ trece prin 2, 3, 4 și ajunge la 5, unde $5\cdot 5=25>17$ oprește ciclul. Se afișează 5, care nu divide 17: rezultatul este un divizor numai dacă numărul nu este prim.

Greșeli frecvente

• Greșit: 1 este prim deoarece are doar un divizor.
  Corect: un număr prim are exact doi divizori pozitivi.
• Greșit: 2 este compus fiindcă este par.
  Corect: 2 este singurul număr prim par.
• Greșit: la 49 se pot testa doar divizorii mai mici decât 7.
  Corect: trebuie testat și 7.

Înainte și după