Grade 9 · Divisibility and prime numbersCitește în română

Sum of divisors

Original: Suma divizorilor

O(√n)C++1738 lines2 examples

The idea

We add the divisors in pairs (d and n / d) for d * d <= n; when n is a perfect square, the root is added only once.

Original description (Romanian)

Adunăm divizorii în perechi (d și n / d) pentru d * d <= n; când n este pătrat perfect, rădăcina se adună o singură dată.

Complexity
O(√n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

12

Expected output

28
Example 2

Input

16

Expected output

31

The code

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

suma-divizorilor.cpp
/*
 * Titlu: Suma divizorilor
 * Clasa: 9
 * Capitol: Divizibilitate și numere prime
 * Descriere: Adunăm divizorii în perechi (d și n / d) pentru d * d <= n; când
 *            n este pătrat perfect, rădăcina se adună o singură dată.
 * Complexitate: O(√n)
 *
 * Exemplu
 * Intrare: 12
 * Ieșire: 28
 *
 * Exemplu
 * Intrare: 16
 * Ieșire: 31
 */
#include <iostream>
using namespace std;

int main()
{
    long long n, suma = 0;
    cin >> n;
    for (long long d = 1; d * d <= n; d++)
    {
        if (n % d == 0)
        {
            suma = suma + d;
            if (d * d != n)
            {
                suma = suma + n / d;
            }
        }
    }
    cout << suma << '\n';
    return 0;
}

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