How do you count all divisors of a number from its prime factorization?

## The formula Every integer `n > 1` has a unique prime factorization ``` n = p1^e1 * p2^e2 * ... * pk^ek ``` and the number of positive divisors of `n` is ``` d(n) = (e1 + 1) * (e2 + 1) * ... * (ek + 1) ``` ## Why the plus-one, and why a product A divisor of `n` cannot contain a prime that `n` does not, and cannot contain any prime more times than `n` does. So building a divisor is a sequence of independent choices: for `p1` pick an exponent in `0..e1` (`e1 + 1` options), for `p2` pick one in `0..e2`, and so on. Independent choices multiply, so the total is the product of the option counts. The `+1` is the option of leaving that prime out entirely — the choice that gives you 1 when taken for every prime, and `n` when you take the maximum everywhere. The reason each choice yields a *distinct* divisor, and every divisor arises from exactly one choice, is unique factorization: two different exponent tuples cannot describe the same integer. That is what turns a counting-of-choices argument into an exact divisor count rather than an upper bound. Worked example, framed as a catalog problem: a batch of 720 items must be split into equal-sized groups. `720 = 2^4 * 3^2 * 5^1`, so `d(720) = 5 * 3 * 2 = 30` — thirty group sizes divide it evenly, from 1 up to 720. If the business rule excludes the degenerate splits (one group, or groups of one), subtract the two extremes and report 28. Notice how much cheaper that is than testing all 720 candidate sizes. ## Two wrong answers this question is designed to catch 1. **"Count the prime factors."** `720` has three *distinct* primes and seven prime factors *with multiplicity*; neither number is 30. Confusing "how many primes" with "how many divisors" is the most common slip. 2. **"Loop from 1 to n and count what divides."** Correct but O(n). If you only need the divisors and not the factorization, the divisor-pairing fact gives a much better loop: walk `i` from 1 while `i * i <= n`, and for each `i` that divides `n`, record both `i` and `n / i`, taking care to record the root only once when `i * i == n`. That is O(sqrt(n)) and produces the actual list, not just the count. ## Odd divisor counts `d(n)` is a product of `(ei + 1)` terms, and a product is odd only when every factor is odd — meaning every `ei` is even, which is exactly the condition for `n` to be a perfect square. This is the clean explanation for the classic observation that divisors pair up `(d, n/d)` and the pairing leaves one element unmatched precisely when `d = n/d`. Interviewers like it because the same conclusion falls out of two different arguments, and a candidate who can give both has actually understood the structure. ## Cost, and how to make it cheap in bulk Getting the factorization at all is the expensive step, not the multiplication afterward. - **One value:** trial-divide by candidates while the candidate squared does not exceed the remaining cofactor, dividing out each prime completely and counting its exponent as you go. Whatever is left above 1 at the end is a single remaining prime factor with exponent 1. Cost O(sqrt(n)). - **Many values in a bounded range:** run a sieve variant that, instead of a boolean flag, stores for each index its *smallest prime factor*. Then factoring any value in the range means repeatedly dividing by its stored smallest factor — at most `log2(n)` steps, since each division at least halves the value. For a nightly job scoring ten thousand catalog batch sizes below a million, this converts ten thousand square-root scans into one near-linear pass plus ten thousand tiny walks. ## Scale intuition worth carrying Divisor counts stay small even when `n` is huge: values below a billion can have more than a thousand divisors, but no more — the count grows far slower than `n`, because pushing it up requires spending many distinct small primes. So enumerating divisors is usually cheap once you have them; the factorization dominates. And when you only need a *count*, never materialise the list. ## The related formula, in one line The same choice-multiplication argument gives the *sum* of divisors as a product of geometric series, one per prime: `(1 + p + p^2 + ... + p^e)` multiplied across the primes. If you can derive the count, you can derive the sum, and interviewers who ask the first sometimes ask the second to see whether the argument was understood or memorised.