Suma divizorilor unui număr în C++

Divizorii pozitivi ai lui 12 sunt 1, 2, 3, 4, 6 și 12. Suma lor este 28. Nu trebuie să verificăm toate numerele până la 12: fiecare divizor mic formează o pereche cu un divizor mare, iar produsul lor este numărul inițial.

Cerință și domeniu

Citim un număr natural n, cu 1≤n≤10^9. Afișăm suma tuturor divizorilor pozitivi, inclusiv 1 și n. Aceasta nu este suma divizorilor proprii, care exclude numărul însuși. Folosim long long pentru sumă și pentru operațiile intermediare. Chiar limita foarte largă n·n≤10^18 arată că suma încape în tip pentru acest domeniu.

Perechi de divizori

Pentru 12, perechile sunt (1,12), (2,6) și (3,4). Când d divide exact numărul, adăugăm d și n/d. Ne oprim când d depășește radicalul, deoarece toate perechile au fost deja găsite.

Fiecare pereche contribuie o singură dată. Pentru 12, suma finală este 28.Mărește schema ↗

Pentru 36 apare perechea (6,6). Aceasta conține un singur divizor distinct, deci adăugăm 6 o singură dată. Condiția d diferit de n/d este necesară tocmai pentru pătratele perfecte. Testarea numai pe numere care nu sunt pătrate poate ascunde această eroare.

Program complet C++17

#include <iostream>
using namespace std;
int main(){
    long long n; cin>>n;
    long long suma=0;
    for(long long d=1;d<=n/d;++d){
        if(n%d==0){
            suma+=d;
            if(d!=n/d) suma+=n/d;
        }
    }
    cout<<suma<<'\n';
}

Corectitudine și complexitate

Orice divizor d are perechea n/d. Cel puțin unul dintre cei doi nu depășește radicalul, deci bucla întâlnește fiecare pereche. Perechile sunt disjuncte, cu excepția egalității tratate separat. Prin urmare, fiecare divizor este adăugat exact o dată.

Condiția d≤n/d evită calcularea pătratului lui d. Ea este validă pentru d pozitiv, așa cum pornește bucla. Timpul este O(√n), iar memoria auxiliară O(1). Nu există un tablou de divizori și nu este necesară sortarea lor.

Exersează

Pentru 1, suma este 1. Pentru 13, un număr prim, suma este 14. Pentru 36, suma este 91. Verifică manual ultimul rezultat din lista 1,2,3,4,6,9,12,18,36. Ca extensie, cere suma divizorilor proprii și scade n numai după ce ai calculat suma completă.

Continuă cu divizibilitatea, descompunerea în factori primi și tipurile numerice.

Întrebări frecvente

Cum calculez suma divizorilor fără să îi stochez?

Parcurge candidații până la radical și adună perechile d și n/d pentru fiecare împărțire exactă. Când cele două valori coincid, adaugă valoarea o singură dată.

Se include numărul însuși în suma divizorilor?

Da în această cerință. Pentru suma divizorilor proprii, numărul însuși este exclus. Diferența dintre cele două rezultate este exact n.

De ce trebuie testat un pătrat perfect?

El are un divizor egal cu perechea sa, radicalul întreg. Testul descoperă implementările care adaugă acest divizor de două ori.