
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