Numere prietene: verificare prin sume de divizori C++

Numerele 220 și 284 sunt prietene: suma divizorilor proprii ai lui 220 este 284, iar suma divizorilor proprii ai lui 284 este 220. Relația cere două verificări. Faptul că suma divizorilor primului număr este al doilea nu demonstrează automat și sensul invers.

Definiție și intrare

Citim două numere naturale a și b, fiecare între 1 și 10^9. Afișăm DA dacă sunt distincte și fiecare este suma divizorilor proprii ai celuilalt; altfel afișăm NU. Un divizor propriu pozitiv este un divizor mai mic decât numărul. Numărul însuși nu intră în sumă.

Pentru 220, lista este 1,2,4,5,10,11,20,22,44,55,110. Suma este 284. Pentru 284, divizorii proprii sunt 1,2,4,71,142, cu suma 220. Aceste liste oferă un răspuns calculat independent, util pentru verificarea programului.

Perechea este validă numai dacă ambele egalități sunt adevărate și numerele diferă.Mărește schema ↗

O funcție cu un singur rol

Funcția proprii(n) returnează suma cerută. Găsește divizorii în perechi d și n/d până la radical. Adaugă un termen numai dacă este mai mic decât n și nu îl dublează când cei doi termeni coincid. Pentru n=1, suma este zero, deoarece nu există divizori pozitivi mai mici decât 1.

Funcția principală verifică distinctivitatea și cele două egalități. Separarea calculului sumei de verificarea relației face mai ușor de testat fiecare parte: poți verifica întâi proprii(220), apoi proprii(284), înainte de condiția finală.

Program complet C++17

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

De ce verificăm numere distincte

Numărul 6 este egal cu suma propriilor divizori 1+2+3. El este perfect, dar perechea 6 și 6 nu este o pereche de numere prietene în definiția aleasă. Condiția a diferit de b separă cele două proprietăți.

Timpul total este O(√a+√b), iar memoria auxiliară O(1). Nu construim listele divizorilor în program; acestea au fost afișate în explicație pentru a face verificarea transparentă. Pentru domeniul declarat, sumele și calculele încap în long long.

Exersează

Verifică 220 și 284 în ambele ordini: rezultatul este DA. Pentru 6 și 6, răspunsul este NU. Pentru 10 și 8, prima sumă este 8, dar suma divizorilor proprii ai lui 8 este 7, deci răspunsul final este NU. Acesta este testul care descoperă verificarea într-un singur sens.

Continuă cu divizibilitatea, funcții și valori returnate și deciziile logice.

Întrebări frecvente

Ce sunt numerele prietene?

Două numere naturale distincte pentru care suma divizorilor proprii ai fiecăruia este egală cu celălalt. Exemplul clasic verificat în lecție este perechea 220 și 284.

De ce nu sunt 6 și 6 o pereche de numere prietene?

Definiția cere numere distincte. Numărul 6 este perfect, fiind egal cu suma divizorilor săi proprii, dar această proprietate nu formează o pereche de numere diferite.

Ajunge să verific suma divizorilor unui singur număr?

Nu. Pentru 10 suma divizorilor proprii este 8, dar pentru 8 suma este 7, nu 10. Trebuie verificate ambele egalități.