Counting Divisors

Counting Divisors
CSES medium

You are given \(n\) integers. For each of them, find the number of its divisors. For example, \(18\) has \(6\) divisors: \(1, 2, 3, 6, 9, 18\).

Constraints:

  • \(1 \le n \le 10^5\)
  • \(1 \le x \le 10^6\)

Input:

  • First line: integer \(n\).
  • Next \(n\) lines: one integer \(x\) per line.

Output:

  • For each integer, one line with the number of its divisors.

Example:

Input:

3
16
17
18

Output:

5
2
6
Solution

Counting the divisors of each number with the \(O(\sqrt{x})\) method takes up to \(10^5 \cdot 10^3 = 10^8\) steps. Here is a faster way.

If the prime factorization of \(x\) is

\[ x = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}, \]

then every divisor of \(x\) is \(p_1^{f_1} \cdot p_2^{f_2} \cdots p_k^{f_k}\) with \(0 \le f_i \le e_i\). There are \(e_i + 1\) choices for each exponent \(f_i\), so by the rule of product the number of divisors is

\[ (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1). \]

For example, \(18 = 2^1 \cdot 3^2\) has \((1 + 1) \cdot (2 + 1) = 6\) divisors.

We factorize each number with the smallest prime factor (SPF) sieve from the lesson on prime factorization. The sieve is computed once, in \(O(\text{MAXN} \log \log \text{MAXN})\) time, and then each factorization takes \(O(\log x)\) time.

#include <iostream>
using namespace std;

const int MAXN = 1000000;
int spf[MAXN + 1];

void sieve() {
    // Initialize: smallest prime factor of i is i itself
    for (int i = 1; i <= MAXN; i++) spf[i] = i;

    for (int i = 2; i * i <= MAXN; i++) {
        if (spf[i] == i) {  // If i is prime
            for (int j = i * i; j <= MAXN; j += i) {
                // Mark smallest factor for j if not marked yet
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

int count_divisors(int x) {
    int result = 1;
    while (x != 1) {
        int p = spf[x];

        // e = the exponent of p in x
        int e = 0;
        while (x % p == 0) {
            x /= p;
            e++;
        }

        result *= e + 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cout << count_divisors(x) << "\n";
    }
}