Number of Divisors / Sum of Divisors

How to compute the number of divisors d(n) and the sum of divisors σ(n) for a given n.

This lesson follows CP-Algorithms — Number of divisors / sum of divisors.

Number of divisors

Every divisor’s prime factors form a submultiset of those of n. Example: 6 = 2·3 divides 60 = 2²·3·5.

If n = p₁^{e₁} · p₂^{e₂} · … · pₖ^{eₖ} with distinct primes, for each pᵢ you may use the exponent 0,1,…,eᵢ — eᵢ + 1 choices. Hence

d(n) = (e₁ + 1)(e₂ + 1)…(eₖ + 1)

One-prime case n = p^e: divisors 1, p, …, p^e → e+1 of them.

Two-prime case: arrange divisors in an (e₁+1) × (e₂+1) table (rows powers of p₁, columns powers of p₂). Count = product of side lengths. Same idea for more primes.

long long numberOfDivisors(long long num) {
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
            total *= e + 1;
        }
    }
    if (num > 1) total *= 2;
    return total;
}

Time: O(√n) trial factorization (same shell as factoring).

Sum of divisors

Same factorization; sum the table instead of counting cells.

For n = p^e:

1 + p + … + p^e = (p^{e+1} − 1) / (p − 1)

For several primes, multiplicativity gives the product of geometric sums:

σ(n) = Πᵢ (pᵢ^{eᵢ+1} − 1) / (pᵢ − 1)

long long SumOfDivisors(long long num) {
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
            long long sum = 0, pow = 1;
            do {
                sum += pow;
                pow *= i;
            } while (e-- > 0);
            total *= sum;
        }
    }
    if (num > 1) total *= (1 + num);
    return total;
}

Watch overflow: intermediate pow / total may need __int128 for large n.

Multiplicative functions

f is multiplicative if gcd(a,b)=1 ⇒ f(a·b) = f(a)·f(b).

Both d and σ are multiplicative (formulas above are exactly the prime-power values extended by multiplicativity). Dirichlet convolution of multiplicative functions stays multiplicative — useful in more advanced divisor-sum problems.

🧪 d(60) and σ(60)

Check: divisor functions

Quiz

d(n) and σ(n)

1 / 4

If n = p₁^{e₁}…pₖ^{eₖ}, then d(n) equals…

Pick an answer to see if you are right.

Practice drills

Activity: Count divisors

Input: n (1 ≤ n ≤ 10¹²). Print d(n).

Practice problems

From CP-Algorithms:

Cheat sheet

Idea	Takeaway
Factor	`n = Π pᵢ^{eᵢ}`
`d(n)`	`Π (eᵢ + 1)`
`σ(n)`	`Π (pᵢ^{eᵢ+1}−1)/(pᵢ−1)`
Time	`O(√n)` via trial factor
Multiplicative	`gcd(a,b)=1 ⇒ f(ab)=f(a)f(b)`
Both	`d` and `σ` are multiplicative