Introduction

Counting the divisors of an integer is a classic number-theory problem with direct algorithmic solutions. The simplest method checks all numbers up to n, but the more useful approaches either exploit divisor pairs up to sqrt(n) or use prime factorization to compute the divisor count directly.

The Pairing Insight

If d divides n, then n / d also divides n. Divisors therefore come in pairs around the square root.

For example, divisors of 36 include:

• '1 and 36'
• '2 and 18'
• '3 and 12'
• '4 and 9'
• '6 and 6'

This means you only need to test candidates up to sqrt(n), not all the way up to n.

Square-Root Counting Algorithm

A direct optimized algorithm is:

1. loop i from 1 to sqrt(n)
2. if i divides n, count one divisor pair
3. if i * i == n, count only one instead of two

1import math
2
3
4def count_divisors_sqrt(n):
5    count = 0
6    limit = int(math.isqrt(n))
7
8    for i in range(1, limit + 1):
9        if n % i == 0:
10            count += 1 if i * i == n else 2
11
12    return count
13
14
15print(count_divisors_sqrt(36))
16print(count_divisors_sqrt(12))

This runs in O(sqrt(n)) time and is often good enough for single queries.

Prime Factorization Formula

If you need a more number-theoretic method, factor the number into primes.

If:

• 'n = p1^a1 * p2^a2 * ... * pk^ak'

then the number of positive divisors is:

• '(a1 + 1) * (a2 + 1) * ... * (ak + 1)'

For example:

• '36 = 2^2 * 3^2'
• divisor count = (2 + 1) * (2 + 1) = 9

That works because every divisor is formed by choosing the exponent of each prime independently from 0 through the prime’s exponent in n.

Factorization-Based Implementation

1
2def count_divisors_factorization(n):
3    total = 1
4    x = n
5    p = 2
6
7    while p * p <= x:
8        exponent = 0
9        while x % p == 0:
10            x //= p
11            exponent += 1
12        if exponent > 0:
13            total *= (exponent + 1)
14        p += 1 if p == 2 else 2
15
16    if x > 1:
17        total *= 2
18
19    return total
20
21
22print(count_divisors_factorization(36))
23print(count_divisors_factorization(72))

This is especially nice when you also want the prime factorization for other work.

Which Method Should You Use

A practical rule is:

• use the square-root loop for simple one-off calculations
• use factorization if you also need prime exponents or many related number-theory results

Both are vastly better than testing every number up to n.

Complexity Notes

The square-root counting method is clearly O(sqrt(n)). The factorization method is also O(sqrt(n)) in a basic implementation, though its constant factors differ and it often feels more elegant mathematically.

If you must answer divisor-count queries for many numbers, preprocessing with a sieve can be even better than factoring each number independently.

Common Pitfalls

The most common mistake is double-counting the square root for perfect squares. For 36, the divisor 6 should be counted once, not twice.

Another mistake is using the factorization formula without fully decomposing the number into prime powers. The formula applies to prime exponents, not to arbitrary factors.

A third issue is ignoring edge cases such as n = 1. The number 1 has exactly one positive divisor: itself.

Summary

• Divisors come in pairs around sqrt(n).
• A simple optimized loop counts divisors in O(sqrt(n)) time.
• Prime factorization gives a direct divisor-count formula using exponents.
• Perfect squares need special handling so the square root is not double-counted.
• Choose the method based on whether you need just the count or also the factorization.