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

Number of divisors

Original: Numărul divizorilor

O(√n)C++1742 lines2 examples

The idea

For every d with d * d <= n that divides n we count two divisors, d and n / d, except when d * d == n, when the two coincide.

Original description (Romanian)

Pentru fiecare d cu d * d <= n care divide n numărăm doi divizori, d și n / d, cu excepția cazului d * d == n, când cei doi coincid.

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

Examples

Example 1

Input

36

Expected output

9
Example 2

Input

1

Expected output

1

The code

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

numarul-divizorilor.cpp
/*
 * Titlu: Numărul divizorilor
 * Clasa: 9
 * Capitol: Divizibilitate și numere prime
 * Descriere: Pentru fiecare d cu d * d <= n care divide n numărăm doi divizori,
 *            d și n / d, cu excepția cazului d * d == n, când cei doi coincid.
 * Complexitate: O(√n)
 *
 * Exemplu
 * Intrare: 36
 * Ieșire: 9
 *
 * Exemplu
 * Intrare: 1
 * Ieșire: 1
 */
#include <iostream>
using namespace std;

int main()
{
    long long n;
    int nrDiv = 0;
    cin >> n;
    for (long long d = 1; d * d <= n; d++)
    {
        if (n % d == 0)
        {
            if (d * d == n)
            {
                nrDiv = nrDiv + 1;
            }
            else
            {
                nrDiv = nrDiv + 2;
            }
        }
    }
    cout << nrDiv << '\n';
    return 0;
}

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