Number of Divisors and Sum of Divisors

From the prime factorization n = p^e × q^f …, finds the number of divisors as (e+1)(f+1)… and their sum as (1 + p + … + p^e)(1 + q + … + q^f)….

Explanation

You do not have to hunt for divisors one at a time. Once the prime factorization is known, both the number of divisors and their total come out of a simple product. Suppose $n = p^e \times q^f \times \cdots$ .

The number of divisors $d(n)$ is found by adding 1 to each exponent and multiplying.

d(n) = (e+1)(f+1)\cdots

The sum of the divisors $\sigma(n)$ multiplies together, for each prime, the total of its powers from 1 up to $p^e$ .

\sigma(n) = (1 + p + \cdots + p^e)(1 + q + \cdots + q^f)\cdots

$n$ — the integer to examine, 1 or more
$p$ , $q$ — the prime factors of $n$
$e$ , $f$ — the exponent on each prime

The count formula makes sense once you picture how a divisor gets built: choose how many copies of $p$ to take, anywhere from 0 to $e$ , then do the same for $q$ , and so on. That is $e + 1$ choices for $p$ , and every combination of choices lands on a different divisor.

Example

Take $n = 36$ . Since $36 = 2^2 \times 3^2$ :

d(36) = (2+1)(2+1) = 9

\sigma(36) = (1 + 2 + 4)(1 + 3 + 9) = 7 \times 13 = 91

And indeed the divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36. Nine of them, adding to 91.

Notes

The count includes both 1 and $n$ itself.
A number with exactly two divisors is prime, since 1 and itself are the only ones.
The count is odd only when $n$ is a perfect square. Divisors normally come in pairs, $d$ alongside $\dfrac{n}{d}$ , but a square has a middle divisor, $\sqrt{n}$ , that pairs with itself and leaves the total odd. That is why $36 = 6^2$ has 9 divisors.
Subtract $n$ from the sum to get the total of its proper divisors. The numbers for which that total equals $n$ are the perfect numbers.