Număr perfect în C++: suma divizorilor proprii

Un număr natural pozitiv este perfect dacă este egal cu suma divizorilor săi pozitivi mai mici decât el. Numărul 6 este perfect: 1+2+3=6. Numărul 8 nu este: 1+2+4=7. Nu confundăm această proprietate cu faptul că un număr este pătrat perfect.

Cerință și limite

Citim un întreg n, cu 1 ≤ n ≤ 10^9. Afișăm DA dacă este perfect și NU în caz contrar. Divizorii proprii exclud numărul însuși. Pentru n=1, nu există niciun divizor pozitiv mai mic, suma este 0 și răspunsul este NU.

Căutăm perechi, nu toate valorile până la n

Dacă d divide n, atunci n/d este tot divizor. Pentru 28, perechile sunt (1,28), (2,14) și (4,7). Ignorăm 28, dar adunăm 1,2,14,4,7 și obținem 28. Este suficient să încercăm d până la rădăcina pătrată: cel puțin un membru al fiecărei perechi este cel mult această rădăcină.

Inițializăm suma cu 1 numai după ce am tratat n=1. Începem căutarea de la 2, astfel încât n să nu ajungă accidental în sumă. Dacă d=n/d, adunăm d o singură dată. Pentru 36, perechea (6,6) nu reprezintă doi divizori diferiți.

Perechile de divizori ale lui 28 sunt (1,28), (2,14) și (4,7). Excludem 28; suma celorlalți este 28.Mărește schema ↗

Program complet

#include <iostream>
using namespace std;
int main() {
    long long n; cin >> n;
    if(n==1) { cout << "NU\n"; return 0; }
    long long suma=1;
    for(long long d=2; d<=n/d; ++d) {
        if(n%d==0) {
            suma+=d;
            if(d!=n/d) suma+=n/d;
        }
    }
    cout << (suma==n ? "DA\n" : "NU\n");
}

Condiția d<=n/d exprimă aceeași limită ca d·d≤n, fără înmulțirea din condiție. Împărțirea este sigură deoarece d începe de la 2. Tipul long long păstrează și suma intermediară; nu alegem tipul doar după n.

De ce nu pierdem divizori

Orice divizor mai mare decât rădăcina are partenerul mai mic decât rădăcina. Bucla îl întâlnește pe acel partener și adaugă ambele valori. Excepția rădăcinii exacte este tratată separat. Numărul încercărilor crește proporțional cu rădăcina lui n, deci timpul este O(√n), iar memoria suplimentară este O(1), câteva variabile.

Exersează

Pentru 1, 6, 28 și 36 obții, în ordine, NU, DA, DA, NU. Suma divizorilor proprii ai lui 36 este 55; verifică această valoare pe hârtie ca să detectezi dublarea lui 6. Extinde afișarea cu suma calculată, fără să schimbi definiția divizorului propriu.

Revezi divizibilitatea, sumele și numărările și descompunerea în factori primi.

Întrebări frecvente

Ce este un număr perfect?

Un număr natural pozitiv egal cu suma divizorilor săi pozitivi mai mici decât el. De exemplu, 6 este perfect deoarece 1+2+3=6. Proprietatea diferă de aceea de pătrat perfect.

Este 1 un număr perfect?

Nu. Numărul 1 nu are divizori pozitivi mai mici decât el, deci suma divizorilor proprii este 0. Cum 0 nu este egal cu 1, răspunsul este negativ.

De ce verificăm divizorii numai până la radical?

Divizorii se grupează în perechi d și n/d. După radical, perechile au fost deja descoperite. La un pătrat perfect, cei doi divizori din perechea centrală sunt egali și trebuie adăugați o singură dată.