Divizorii unui număr

Un întreg pozitiv $d$ este divizor al lui $n$ dacă restul împărțirii lui $n$ la $d$ este zero. Pentru 12, divizorii pozitivi sunt 1, 2, 3, 4, 6 și 12. În acest curs, un divizor propriu este strict între 1 și $n$; pentru 12, divizorii proprii sunt 2, 3, 4 și 6. Divizorii pozitivi apar în perechi: $1\cdot 12$, $2\cdot 6$, $3\cdot 4$. Această observație reduce căutarea până la rădăcina pătrată a numărului.

În Python, 12 % 3 == 0 este adevărat: 3 divide 12 fără rest. Testând valorile de la 1 la 12 obții divizorii 1, 2, 3, 4, 6, 12.

Spunem că $d$ este divizor al lui $n$ dacă $n\mathrm{mod}d=0$. Divizorii pozitivi ai unui număr apar în perechi $(d;n/d)$: dacă $d\cdot e=n$, unul dintre ei este cel mult $\sqrt{n}$. Pentru $n=12$ perechile sunt $(1;12)$, $(2;6)$ și $(3;4)$, iar divizorii mai mici decât $\sqrt{12}\approx 3,46$ sunt 1, 2 și 3. De aceea e suficient să testezi valorile $d$ cu $d\cdot d\le n$ și să tratezi fiecare divizor găsit împreună cu perechea lui. Dacă $d\cdot d=n$, perechea coincide cu $d$ și numărul se ia o singură dată. Divizorii 1 și $n$ se numesc improprii; ceilalți sunt divizori proprii. Testul d <= n / d este echivalent cu $d\cdot d\le n$, dar nu depășește tipul întreg la numere mari.

Exemplul 1 — numărul și suma divizorilor lui 36. Valorile lui $d$ sunt 1, 2, 3, 4, 5 și 6.

1. $d=1$: divizor, pereche $(1;36)$, contorul crește cu 2, suma cu $1+36=37$.
2. $d=2$: pereche $(2;18)$, contor 4, suma $37+20=57$.
3. $d=3$: pereche $(3;12)$, contor 6, suma $57+15=72$.
4. $d=4$: pereche $(4;9)$, contor 8, suma $72+13=85$.
5. $d=5$ nu divide 36.
6. $d=6$: $6\cdot 6=36$, un singur divizor, contor 9, suma $85+6=91$.

#include <iostream>
using namespace std;
int main() {
    int n = 36, cnt = 0, suma = 0;
    for (int d = 1; d <= n / d; ++d) {
        if (n % d == 0) {
            cnt += (d == n / d) ? 1 : 2;
            suma += d + (d == n / d ? 0 : n / d);
        }
    }
    cout << cnt << ' ' << suma;
    return 0;
}

Programul afișează 9 91. Numărul 36 are un număr impar de divizori pentru că este pătrat perfect; orice alt număr natural are un număr par de divizori.

Exemplul 2 — afișarea divizorilor în ordine crescătoare. Pentru $n=12$, parcurgi mai întâi $d$ de la 1 în sus și afișezi divizorii mici, apoi $d$ de la rădăcină în jos și afișezi perechile mari $n/d$, sărind peste pătratul perfect:

int n = 12, r = 1;
while ((r + 1) * (r + 1) <= n) ++r;   // r = [radical din n]
for (int d = 1; d <= r; ++d)
    if (n % d == 0) cout << d << ' ';
for (int d = r; d >= 1; --d)
    if (n % d == 0 && d * d != n) cout << n / d << ' ';

Prima parcurgere afișează divizorii mici 1, 2, 3. A doua merge în sens invers și afișează perechile lor mari $12/3=4$, $12/2=6$, $12/1=12$, sărind peste pătratul perfect, unde perechea ar repeta divizorul. Rezultatul este 1 2 3 4 6 12, adică divizorii în ordine crescătoare.

Un număr natural este perfect dacă este egal cu suma divizorilor săi proprii și a lui 1 fără el însuși; de exemplu $28=1+2+4+7+14$. Aceeași parcurgere până la $\sqrt{n}$ îl poate verifica fără să testeze toate valorile până la $n$.

Exemplul 3 — numărul divizorilor din descompunerea în factori primi. Dacă $n=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$, numărul divizorilor pozitivi este $(e_1+1)(e_2+1)\cdots (e_k+1)$. Pentru $360=2^3\cdot 3^2\cdot 5$ rezultă $4\cdot 3\cdot 2=24$ divizori. Parcurgerea cu perechi dă același rezultat: ciclul merge până la $d=18$, pentru că $18\cdot 18=324\le 360<361=19\cdot 19$. Valorile care divid 360 sunt 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 și 18, adică 12 valori. Niciuna nu are $d\cdot d=360$, deci fiecare aduce câte 2 divizori și contorul final este 24.

Exemplul 4 — testul de număr prim. Un număr $n\ge 2$ este prim dacă are exact doi divizori, 1 și $n$. Este suficient să cauți un divizor $d$ cu $2\le d\le \sqrt{n}$. Pentru 97 se testează $d=2,3,\dots ,9$, deoarece $9\cdot 9=81\le 97<100=10\cdot 10$. Niciun $d$ nu dă rest 0, deci 97 este prim.

La numărarea divizorilor, nu dubla rădăcina unui pătrat perfect. Pentru $n=1$ există un singur divizor, 1. Când condiția buclei este d * d <= n, ultima valoare a lui $d$ este $[\sqrt{n}]$, nu $n/2$. Într-un fragment care folosește n % d, valoarea $d=0$ este interzisă. Dacă într-un fragment apar ambele bucle, ca mai sus, ordinea afișării este cea a ciclurilor, nu cea a valorilor. Complexitatea metodei pe perechi este proporțională cu $\sqrt{n}$, iar a celei care testează toate valorile până la $n$ este proporțională cu $n$. Pentru $n=1$ ciclul face o singură iterație, $d=1$, cu $1\cdot 1=n$, adaugă 1 și numărul are un singur divizor. Pentru un număr prim $p$, valoarea $d=1$ adaugă 2, iar celelalte iterații nu găsesc niciun divizor, deci contorul final este 2.

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

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;

• a) 5
• b) 6
• c) 9
• d) 10

Răspunsul corect este c). Ciclul parcurge $d=1,\dots ,6$. Valorile 1, 2, 3 și 4 sunt divizori cu perechi distincte (36, 18, 12, 9) și adaugă câte 2: contorul ajunge la 8. Valoarea 5 nu divide 36. Pentru $d=6$ avem $6\cdot 6=36$, deci se adaugă 1 și $k=9$. Varianta a) numără doar iterațiile care găsesc un divizor mic, adică 1, 2, 3, 4 și 6 fără perechi. Varianta d) numără și rădăcina 6 de două ori.

Greșeli frecvente

• Greșit: 1 are doi divizori pozitivi.
  Corect: are doar divizorul 1.
• Greșit: la 36, perechea lui 6 adaugă încă un 6 distinct.
  Corect: 6 se numără o singură dată.
• Greșit: orice valoare $d$ poate fi folosită la n % d.
  Corect: divizorul trebuie să fie nenul.

Înainte și după