Suma divizorilor unui număr în C++

Dându-se un număr natural n, să se afle suma divizorilor săi.

Exemplu. Pentru n = 20, suma divizorilor este 42 (divizorii acestuia sunt: 1, 2, 4, 5, 10, 20).

Metoda 1 (naivă)

Știm că toți divizorii unui număr se află între 1 și numărul respectiv. Așadar, putem să parcurgem toate numerele d de la 1 la n și să verificăm dacă numărul curent (d) este divizor al lui n (n % d == 0).

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul n
    int n;
    cin >> n;

    //Calculăm suma divizorilor lui n
    int sumdiv = 0;
    for(int d = 1; d <= n; d++) {
        if(n % d == 0) { //Am găsit un nou divizor pentru n
            sumdiv = sumdiv + d;
        }
    }

    //Afișăm suma divizorilor lui n
    cout << sumdiv;
    return 0;
}

Observații

Acest algoritm nu este foarte bun, deoarece parcurge toate numerele de la 1 la n. Spre exemplu, pentru n = 1.000.000.000, se fac un miliard de operații, deși numărul 1.000.000.000 are doar 100 de divizori.

Din fericire, există o metodă mai eficentă.

Metoda 2 (eficientă)

Observăm că divizorii vin în perechi. Dacă d este divizor al lui n, atunci n / d este un număr natural, așadar n / d este un alt divizor al lui n (putem verifica asta calculând d * (n / d) = n).

Mai mult decât atât, divizorii sunt în jurul numărului sqrt(n) — dacă d < sqrt(n), atunci n / d > sqrt(n). Astfel, trebuie să parcurgem numerele doar până la radicalul lui n, considerând atât d, cât și n / d ca și divizori.

Există totuși o excepție: numerele pătrate perfecte. De obicei, numerele au un număr par de divizori (din acest motiv vin în perechi), însă excepție fac pătratele perfecte, unde există un d = sqrt(n). În acest caz, perechea lui d este n / d = n / sqrt(n) = sqrt(n) = d (d este perechea sa). În acest sens, pentru numerele pătrate perfecte, trebuie avut grijă să nu marcăm de două ori radicalul.

Implementare în C++

#include <iostream>
#include <cmath> //Pentru funcția sqrt(), ce extrage rădăcina pătrată a unui număr

using namespace std;

int main()
{
    //Declarăm și citim numărul n
    int n;
    cin >> n;

    //Calculăm suma divizorilor lui n
    int sumdiv = 0;
    for(int d = 1; d <= sqrt(n); d++) {
        if(n % d == 0) { //Am găsit doi divizori pentru n: d și n / d
            sumdiv = sumdiv + d; //Adunăm divizorul d
            if(d != n / d) { //Dacă d nu este radical din n (d nu este perechea sa)
                sumdiv = sumdiv + n / d; //Adunăm perechea lui d, n / d
            }
        }
    }

    //Afișăm suma divizorilor lui n
    cout << sumdiv;
    return 0;
}