Grade 12 · Math for programmingCitește în română

Number and sum of divisors from the prime factorization

Original: Numărul și suma divizorilor din descompunerea în factori primi

O(√n)C++1763 lines4 examples

The idea

If n = p1^e1 * p2^e2 * ... * pk^ek, a divisor chooses for every prime an exponent between 0 and ei, so the number of divisors is (e1 + 1) * (e2 + 1) * ... * (ek + 1). The sum of divisors is the product of the sums 1 + p + p^2 + ... + p^ei. We factorize n by trying the divisors d = 2, 3, ... while d * d ≤ n; whatever remains at the end, if greater than 1, is a prime factor. The program prints the number and the sum of divisors, for n ≤ 10^12.

Original description (Romanian)

Dacă n = p1^e1 * p2^e2 * ... * pk^ek, un divizor alege pentru fiecare prim un exponent între 0 și ei, deci numărul divizorilor este (e1 + 1) * (e2 + 1) * ... * (ek + 1). Suma divizorilor este produsul sumelor 1 + p + p^2 + ... + p^ei. Descompunem n încercând divizorii d = 2, 3, ... cât timp d * d ≤ n; ce rămâne la final, dacă e mai mare decât 1, este un factor prim. Programul afișează numărul și suma divizorilor, pentru n ≤ 10^12.

Complexity
O(sqrt(n))
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

360

Expected output

24 1170
Example 2

Input

1000000000000

Expected output

169 2499694822171
Example 3

Input

999999999989

Expected output

2 999999999990
Example 4

Input

1

Expected output

1 1

The code

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

numarul-de-divizori-din-descompunere.cpp
/*
 * Titlu: Numărul și suma divizorilor din descompunerea în factori primi
 * Clasa: 12
 * Capitol: Matematică pentru programare
 * Descriere: Dacă n = p1^e1 * p2^e2 * ... * pk^ek, un divizor alege pentru fiecare
 *            prim un exponent între 0 și ei, deci numărul divizorilor este
 *            (e1 + 1) * (e2 + 1) * ... * (ek + 1). Suma divizorilor este produsul
 *            sumelor 1 + p + p^2 + ... + p^ei. Descompunem n încercând divizorii
 *            d = 2, 3, ... cât timp d * d ≤ n; ce rămâne la final, dacă e mai mare
 *            decât 1, este un factor prim. Programul afișează numărul și suma
 *            divizorilor, pentru n ≤ 10^12.
 * Complexitate: O(sqrt(n))
 *
 * Exemplu
 * Intrare: 360
 * Ieșire: 24 1170
 *
 * Exemplu
 * Intrare: 1000000000000
 * Ieșire: 169 2499694822171
 *
 * Exemplu
 * Intrare: 999999999989
 * Ieșire: 2 999999999990
 *
 * Exemplu
 * Intrare: 1
 * Ieșire: 1 1
 */
#include <iostream>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    long long nrDiv = 1, sumaDiv = 1;
    for (long long d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
        {
            int e = 0;
            long long putere = 1, suma = 1; // suma = 1 + d + ... + d^e
            while (n % d == 0)
            {
                n /= d;
                e++;
                putere *= d;
                suma += putere;
            }
            nrDiv *= (e + 1);
            sumaDiv *= suma;
        }
    }
    if (n > 1) // a rămas un factor prim, cu exponentul 1
    {
        nrDiv *= 2;
        sumaDiv *= (1 + n);
    }
    cout << nrDiv << ' ' << sumaDiv << '\n';
    return 0;
}

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