Grade 10 · Subprograms (functions)Citește în română

Amicable numbers

Original: Numere prietene

O(√n)C++1754 lines2 examples

The idea

Two numbers a and b are amicable if the sum of the proper divisors of a (the divisors smaller than a) is b and the sum of the proper divisors of b is a. The classic example: 220 and 284. The function sumaDivizoriProprii(x) goes through the divisors in pairs (d and x / d) up to the square root of x.

Original description (Romanian)

Două numere a și b sunt prietene dacă suma divizorilor proprii ai lui a (divizorii mai mici decât a) este b și suma divizorilor proprii ai lui b este a. Exemplul clasic: 220 și 284. Funcția sumaDivizoriProprii(x) parcurge divizorii în perechi (d și x / d) până la radical din x.

Complexity
O(sqrt(a) + sqrt(b))
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

220 284

Expected output

DA
Example 2

Input

10 20

Expected output

NU

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

numere-prietene.cpp
/*
 * Titlu: Numere prietene
 * Clasa: 10
 * Capitol: Subprograme (funcții)
 * Descriere: Două numere a și b sunt prietene dacă suma divizorilor proprii ai lui a
 *            (divizorii mai mici decât a) este b și suma divizorilor proprii ai lui b
 *            este a. Exemplul clasic: 220 și 284. Funcția sumaDivizoriProprii(x)
 *            parcurge divizorii în perechi (d și x / d) până la radical din x.
 * Complexitate: O(sqrt(a) + sqrt(b))
 *
 * Exemplu
 * Intrare: 220 284
 * Ieșire: DA
 *
 * Exemplu
 * Intrare: 10 20
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

long long sumaDivizoriProprii(long long x)
{
    if (x == 1)
        return 0;
    long long s = 1;   // 1 este divizor propriu al oricărui x > 1
    for (long long d = 2; d * d <= x; d++)
    {
        if (x % d == 0)
        {
            s = s + d;
            if (d != x / d)
                s = s + x / d;
        }
    }
    return s;
}

bool suntPrietene(long long a, long long b)
{
    return a != b && sumaDivizoriProprii(a) == b && sumaDivizoriProprii(b) == a;
}

int main()
{
    long long a, b;
    cin >> a >> b;
    if (suntPrietene(a, b))
        cout << "DA\n";
    else
        cout << "NU\n";
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.