Divizorii unui număr: generare, numărare și sumă în O(√n)

Un număr natural d este divizor al lui n dacă n % d == 0. Divizorii lui 12 sunt 1, 2, 3, 4, 6, 12. Divizorii proprii sunt cei diferiți de 1 și de numărul însuși: pentru 12, aceștia sunt 2, 3, 4, 6. La BAC informatică, problemele cu divizori apar atât ca algoritmi de urmărit la Subiectul II, cât și ca subprograme la Subiectul III, unde se cere adesea o soluție eficientă.

Varianta simplă: parcurgerea tuturor valorilor

Cel mai direct mod este să testezi fiecare valoare de la 1 la n:

for (int d = 1; d <= n; d++)
    if (n % d == 0)
        cout << d << " ";

Este corect și afișează divizorii în ordine crescătoare, dar face n pași. O mică îmbunătățire: niciun divizor (în afară de n) nu depășește n / 2, deci poți merge până la n / 2 și să adaugi separat pe n. Tot O(n), doar de două ori mai rapid. Pentru numere de ordinul 10⁹, sau pentru multe numere citite dintr-un fișier, asta nu este suficient.

Ideea eficientă: divizorii vin în perechi

Dacă d este divizor al lui n, atunci și n / d este divizor. Pentru 36:

În fiecare pereche, numărul din stânga este cel mult √n, iar cel din dreapta cel puțin √n. Așa că e suficient să parcurgi d de la 1 cât timp d * d <= n și, pentru fiecare divizor găsit, să-l iei în calcul și pe „partenerul” lui. Numărul de pași scade de la n la √n: pentru 10⁹, de la un miliard la aproximativ 31 623.

Ultimul rând din tabel arată singura capcană: când n este pătrat perfect, perechea (6, 6) conține același divizor de două ori. Dacă nu tratezi cazul, îl numeri dublu.

Numărul de divizori

int nrDivizori(int n)
{
    int nr = 0;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0)
        {
            if (d * d == n)
                nr = nr + 1;   // d și n/d coincid
            else
                nr = nr + 2;   // d și n/d sunt diferiți
        }
    return nr;
}

Pentru 36: d = 1, 2, 3, 4 adaugă câte 2 (total 8), d = 6 adaugă 1, deci 9 divizori. Pentru 12: d = 1, 2, 3 adaugă câte 2, deci 6 divizori (bucla se oprește la d = 3, pentru că 4 · 4 = 16 > 12).

Observă o proprietate utilă la grile: un număr are un număr impar de divizori dacă și numai dacă este pătrat perfect. Exact pentru pătratele perfecte există o pereche „cu un singur element”.

Suma divizorilor

Aceeași structură, dar aduni valorile în loc să le numeri:

long long sumaDivizori(int n)
{
    long long s = 0;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0)
        {
            s = s + d;
            if (d != n / d)
                s = s + n / d;
        }
    return s;
}

Pentru 36: 1 + 36 + 2 + 18 + 3 + 12 + 4 + 9 + 6 = 91. Pentru 12: 1 + 12 + 2 + 6 + 3 + 4 = 28. Suma poate depăși valoarea lui n de câteva ori, de aceea am folosit long long.

Dacă se cere suma divizorilor proprii, scazi din rezultat 1 + n (pentru n > 1). Un număr perfect este egal cu suma divizorilor săi diferiți de el însuși: 6 = 1 + 2 + 3 și 28 = 1 + 2 + 4 + 7 + 14. Cu funcția de mai sus, n este perfect dacă sumaDivizori(n) - n == n.

Afișarea divizorilor în ordine crescătoare

Cu metoda perechilor, divizorii nu ies în ordine: pentru 36 obții 1, 36, 2, 18, 3, 12... Dacă enunțul cere ordinea crescătoare, faci două parcurgeri: prima afișează divizorii mici, crescător, iar a doua merge înapoi și afișează partenerii lor, care vor fi tot crescători.

#include <iostream>
using namespace std;

int main()
{
    int n, d;
    cin >> n;                       // de exemplu 36
    for (d = 1; d * d <= n; d++)
        if (n % d == 0)
            cout << d << " ";       // 1 2 3 4 6
    d--;                            // ultimul d cu d*d <= n
    if (d * d == n)
        d--;                        // nu afișăm radicalul de două ori
    for (; d >= 1; d--)
        if (n % d == 0)
            cout << n / d << " ";   // 9 12 18 36
    return 0;
}

Pentru 36 se afișează 1 2 3 4 6 9 12 18 36. Pentru 12: prima buclă afișează 1 2 3, apoi d revine la 3 (3 · 3 ≠ 12), iar a doua buclă afișează 12 / 3 = 4, 12 / 2 = 6, 12 / 1 = 12.

Legătura cu descompunerea în factori primi

Pentru grile e util să știi și formula: dacă n = p₁^a · p₂^b · …, atunci numărul de divizori este (a + 1)(b + 1)…. De exemplu, 36 = 2² · 3² are (2 + 1)(2 + 1) = 9 divizori, iar 360 = 2³ · 3² · 5 are 4 · 3 · 2 = 24 de divizori. Așa verifici rapid un răspuns fără să listezi toți divizorii.