Video: Suma divizorilor unui număr în C++

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;
}

DS

Autorul acestei lecții

Dominic Satnoianu

Această lecție a fost redactată de către Dominic Satnoianu.

© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.

Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te