Counting and Summing Divisors
Pillar: Set — "The divisors of \(n\) ARE a set. Counting and summing them = applying formulas to the prime factorization SET."
The Setup
Take \(n = 12\). Its divisors are \(1, 2, 3, 4, 6, 12\). That's six of them, and they sum to \(28\).
You could find those by brute force — try every number from \(1\) to \(12\) and check if it divides evenly. But what if \(n = 10^{12}\)? You can't iterate up to a trillion. You need a formula, and the formula comes directly from the prime factorization you built in Ch2 L1.
The key question: given the prime factorization of \(n\), can you compute the number of divisors and the sum of divisors WITHOUT listing them all?
Yes. And the reasoning is pure set thinking.
Number of Divisors: \(\tau(n)\)
Start with the factorization of \(360\):
Every divisor of \(360\) has the form \(2^a \times 3^b \times 5^c\) where:
- \(a\) can be \(0, 1, 2,\) or \(3\) — that's \(4\) choices
- \(b\) can be \(0, 1,\) or \(2\) — that's \(3\) choices
- \(c\) can be \(0\) or \(1\) — that's \(2\) choices
Each choice is independent. Picking \(a = 2\) doesn't restrict what \(b\) or \(c\) can be. Independent choices multiply, so:
That's \(24\) divisors. Let's verify by listing them all.
| \(5^0\) | \(5^1\) | |
|---|---|---|
| \(2^0 \times 3^0\) | \(1\) | \(5\) |
| \(2^0 \times 3^1\) | \(3\) | \(15\) |
| \(2^0 \times 3^2\) | \(9\) | \(45\) |
| \(2^1 \times 3^0\) | \(2\) | \(10\) |
| \(2^1 \times 3^1\) | \(6\) | \(30\) |
| \(2^1 \times 3^2\) | \(18\) | \(90\) |
| \(2^2 \times 3^0\) | \(4\) | \(20\) |
| \(2^2 \times 3^1\) | \(12\) | \(60\) |
| \(2^2 \times 3^2\) | \(36\) | \(180\) |
| \(2^3 \times 3^0\) | \(8\) | \(40\) |
| \(2^3 \times 3^1\) | \(24\) | \(120\) |
| \(2^3 \times 3^2\) | \(72\) | \(360\) |
Count them: \(12\) rows \(\times\) \(2\) columns \(= 24\) divisors. \(\checkmark\)
The general formula: if \(n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}\), then:
This is the Set pillar in action. The prime factorization is a set of independent choices. Counting divisors means counting the elements of the Cartesian product of those choice sets. Cartesian product sizes multiply.
Note: \(\tau(1) = 1\). The number \(1\) has the empty factorization (no primes), and the empty product is \(1\).
Sum of Divisors: \(\sigma(n)\)
Now instead of counting divisors, sum them. The trick: when you expand a product of sums, you get the sum of all products.
Take \(n = 12 = 2^2 \times 3^1\).
The divisors of \(12\) come from choosing an exponent for \(2\) (either \(0, 1,\) or \(2\)) and an exponent for \(3\) (either \(0\) or \(1\)). The sum of all divisors is:
Why does this work? Expanding the product gives every possible term \(2^a \times 3^b\) — and that's exactly every divisor of \(12\). The distributive law does the enumeration for you.
Verify: divisors of \(12\) are \(1, 2, 3, 4, 6, 12\). Sum \(= 1 + 2 + 3 + 4 + 6 + 12 = 28\). \(\checkmark\)
Each factor in the product is a geometric series. For a prime \(p\) with exponent \(a\):
So the general formula is:
Trace it for \(\sigma(360) = \sigma(2^3 \times 3^2 \times 5^1)\):
And \(\sigma(1) = 1\), since the only divisor of \(1\) is itself.
Divisor Enumeration in \(O(\sqrt{n})\)
Sometimes you need the actual list, not just the count or sum. You don't need to check every number up to \(n\). The observation: divisors come in pairs.
If \(i\) divides \(n\), then \(n / i\) also divides \(n\). And one of the pair is \(\leq \sqrt{n}\) while the other is \(\geq \sqrt{n}\).
So iterate \(i\) from \(1\) to \(\sqrt{n}\). Each time \(i \mid n\), record both \(i\) and \(n/i\).
The trap: when \(n\) is a perfect square, \(\sqrt{n}\) pairs with itself. If \(n = 36\) and \(i = 6\), then \(n/i = 6\) too. You must not count it twice.
Trace for \(n = 36\):
| \(i\) | \(i \mid 36\)? | Pair \((i, 36/i)\) |
|---|---|---|
| \(1\) | yes | \((1, 36)\) |
| \(2\) | yes | \((2, 18)\) |
| \(3\) | yes | \((3, 12)\) |
| \(4\) | yes | \((4, 9)\) |
| \(5\) | no | — |
| \(6\) | yes | \((6, 6)\) — same! |
Result: \(\{1, 2, 3, 4, 6, 9, 12, 18, 36\}\) — nine divisors. And \(\tau(36) = \tau(2^2 \times 3^2) = 3 \times 3 = 9\). \(\checkmark\)
Sieve for All \(\tau\) Values in \([1, n]\)
What if you need \(\tau(k)\) for every \(k\) from \(1\) to \(n\)? Factorizing each one individually costs \(O(n\sqrt{n})\). There's a faster way.
For each \(d\) from \(1\) to \(n\), \(d\) is a divisor of \(d, 2d, 3d, \ldots\) Add \(1\) to \(\tau[d]\), \(\tau[2d]\), \(\tau[3d]\), and so on.
The total work is:
That's the harmonic sum from Ch2 L2 — the Shape pillar in action. The same staircase of \(\lfloor n/d \rfloor\) terms that governs sieve performance shows up here.
Sieve for All \(\sigma\) Values
Same structure as the \(\tau\) sieve, but instead of adding \(1\) for each divisor relationship, add \(d\) itself. When \(d\) divides \(m\), \(d\) contributes \(d\) to the sum of divisors of \(m\).
vector<long long> sieveSigma(int limit) {
vector<long long> divisorSum(limit + 1, 0);
for (int divisor = 1; divisor <= limit; divisor++) {
for (int multiple = divisor; multiple <= limit; multiple += divisor) {
divisorSum[multiple] += divisor;
}
}
return divisorSum;
}
Same \(O(n \log n)\) complexity. After this runs, divisorSum[k] holds \(\sigma(k)\) for every \(k\) in \([1, n]\).
Highly Composite Numbers
A brief detour. A highly composite number is one that has more divisors than any smaller positive integer.
The first few: \(1, 2, 4, 6, 12, 24, 36, 48, 60, 120, \ldots\)
Look at \(12\): it has \(6\) divisors. No number less than \(12\) has \(6\) or more. The number \(11\) has \(2\), \(10\) has \(4\), \(9\) has \(3\), \(8\) has \(4\).
These numbers tend to have small, balanced prime exponents — lots of \(2\)s, fewer \(3\)s, even fewer \(5\)s. That maximizes the product \((a_1 + 1)(a_2 + 1) \cdots\) for a given size. You won't see these tested directly in contests, but they're good to know about when estimating worst-case divisor counts. For \(n \leq 10^6\), the maximum number of divisors is \(240\) (achieved by \(720720\)). For \(n \leq 10^9\), it's \(1344\).
The Code
Count Divisors from Factorization
int countDivisors(int number) {
int totalDivisors = 1;
for (int divisor = 2; (long long)divisor * divisor <= number; divisor++) {
int exponent = 0;
while (number % divisor == 0) {
exponent++;
number /= divisor;
}
if (exponent > 0) totalDivisors *= (exponent + 1);
}
if (number > 1) totalDivisors *= 2;
return totalDivisors;
}
When \(n > 1\) remains after the loop, it's a prime with exponent \(1\), contributing a factor of \((1 + 1) = 2\).
Sum Divisors from Factorization
long long sumDivisors(int number) {
long long totalSum = 1;
for (int divisor = 2; (long long)divisor * divisor <= number; divisor++) {
int exponent = 0;
long long primePower = 1;
while (number % divisor == 0) {
exponent++;
primePower *= divisor;
number /= divisor;
}
if (exponent > 0) totalSum *= (primePower * divisor - 1) / (divisor - 1);
}
if (number > 1) totalSum *= (1 + number);
return totalSum;
}
The expression primePower * divisor - 1 computes \(p^{a+1} - 1\). After the while loop, primePower holds \(p^a\), so multiplying by divisor gives \(p^{a+1}\).
Enumerate Divisors in \(O(\sqrt{n})\)
vector<int> enumerateDivisors(int number) {
vector<int> smallDivisors, largeDivisors;
for (int candidate = 1; (long long)candidate * candidate <= number; candidate++) {
if (number % candidate == 0) {
smallDivisors.push_back(candidate);
if (candidate != number / candidate) {
largeDivisors.push_back(number / candidate);
}
}
}
reverse(largeDivisors.begin(), largeDivisors.end());
for (int divisor : largeDivisors) smallDivisors.push_back(divisor);
return smallDivisors;
}
The candidate != number / candidate check handles perfect squares. The result comes out sorted.
Sieve All Tau Values
vector<int> sieveTau(int limit) {
vector<int> numDivisors(limit + 1, 0);
for (int divisor = 1; divisor <= limit; divisor++) {
for (int multiple = divisor; multiple <= limit; multiple += divisor) {
numDivisors[multiple]++;
}
}
return numDivisors;
}
After this, numDivisors[k] \(= \tau(k)\) for all \(k\) in \([1, \text{limit}]\).
Complexity
countDivisors(n),sumDivisors(n): \(O(\sqrt{n})\) time, \(O(1)\) space.enumerateDivisors(n): \(O(\sqrt{n})\) time, \(O(\sqrt{n})\) space (at most \(2\sqrt{n}\) divisors in the output, though usually far fewer).sieveTau(n),sieveSigma(n): \(O(n \log n)\) time, \(O(n)\) space.
Common Mistakes
- Double-counting \(\sqrt{n}\) when \(n\) is a perfect square. If \(n = 36\) and your loop finds \(i = 6\), both \(i\) and \(n/i\) are \(6\). Without the
candidate != number / candidateguard, you count \(6\) twice and get \(10\) divisors instead of \(9\). - Off-by-one in the geometric sum formula. The formula is \(\frac{p^{a+1} - 1}{p - 1}\), not \(\frac{p^a - 1}{p - 1}\). The exponent in the numerator is \(a + 1\), one more than the highest power in the factorization. Mess this up and every \(\sigma\) value is wrong.
- Forgetting that \(\tau(1) = 1\) and \(\sigma(1) = 1\). The number \(1\) has exactly one divisor (itself), and that divisor sums to \(1\). Your factorization loop won't enter the while body for \(n = 1\), so make sure
totalDivisorsandtotalSumstart at \(1\), not \(0\).
Quick Recap
- \(\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)\): each prime independently contributes choices, and independent choices multiply. This is the Cartesian product of the exponent choice sets.
- \(\sigma(n) = \prod \frac{p_i^{a_i+1} - 1}{p_i - 1}\): expand the product of geometric series to get the sum of all divisors without listing them.
- Enumerate all divisors in \(O(\sqrt{n})\) by pairing \(i\) with \(n/i\). Guard against the perfect square case.
- Sieve \(\tau\) or \(\sigma\) for all values in \([1, n]\) in \(O(n \log n)\) using the harmonic sum pattern from Ch2 L2.
- Highly composite numbers maximize \(\tau(n)\) for their size — useful for estimating worst-case divisor counts.
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Sum of Divisors | cses.fi/problemset/task/1082 | Medium | Floor staircase + divisor sum |
| CSES — Divisor Analysis | cses.fi/problemset/task/2182 | Medium | \(\tau\), \(\sigma\), product of divisors from factorization |
| LC 1492 — The kth Factor of n | leetcode.com/problems/the-kth-factor-of-n | Easy | Divisor enumeration in \(O(\sqrt{n})\) |