Limbajul C++. Numere prietene.

Un enunt clasic: 

"Dat fiind un numar intreg fixat ca limita, sa se gaseasca toate numerele prietene pana la aceasta limita, inclusiv."

Numerele naturale x si y sunt prietene daca toti divizorii lui x, exclusiv x, inclusiv 1, insumati, egaleaza y si reciproc.

Prima pereche de numere prietene este (220, 284) pentru ca suma divizorilor lui 220, 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110, este egala cu 284.

Divizorii lui 284 sunt 1, 2, 4, 71 si 142 iar suma lor este 220.

In codul urmator, functia isFriend(...) testeaza secvential toate numerele intre 1 si numarul-limita, inclusiv, calculand suma divizorilor, sum_div. Numarului obtinut astfel i se calculeaza, de asemenea, divizorii iar daca suma lor este egala cu numarul natural luat ca argument la iteratia curenta, i, atunci cele doua numere, i si sum_div, sunt prietene.

Variabila globala int last memoreaza ultimul numar prieten determinat ca suma a divizorilor la o iteratie oarecare i.

Acesta este "sarit" cand variabila-contor ajunge la el, pentru evitarea duplicarii perechilor.

isFriend(...) intoarce 1 daca este gasita o pereche de numere prietene si 0 in caz contrar, ceea ce permite determinarea numarului de perechi ca suma a rezultatelor intoarse pe parcursul iteratiilor.

Codul si prinscreenul:

#include <iostream>

using namespace std;

int last = 0;

int isFriend(int x)

{

            int sum_div = 0;

            int sum_div1 = 0;

            for(int i = 1; i <= x/2; i++)

            {

                        if(!(x%i)) sum_div += i;

            }

            for(int i = 1; i <= sum_div/2; i++)

            {

                        if(!(sum_div%i)) sum_div1 += i;

            }

            if(sum_div1 == x && x != sum_div)

    {

     last = sum_div;

     cout <<"Numerele " << x << " si " << sum_div <<" sunt prietene.\n";

     return 1;

    }

    else return 0;

           

}

int main()

{

            int limit, pairs = 0;

            cout <<"\nIntroduceti un numar-limita. Vom gasi numerele prietene pana la el, inclusiv.\n";

            cin >> limit;

            for(int i = 1; i <= limit; i++)

    {

       if(i == last) continue;

       else pairs += isFriend(i);

    }

            cout <<"\nAu fost gasite " << pairs <<" perechi de numere prietene.";

            return 0;

}