Counting Divisors
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";
}
}