Counting divisors of a number in \(O(N^{1/3})\)

2022/06/01

Note: For discussion, please jump to the blog on Codeforces. This post is re-written and hence a bit more refined, but carries the same underlying idea.

Pre-requisites

Problem

Given a number \(N\), count the number of divisors of \(N\).

For example:

Naive Solution - Factorization

One straightforward solution is to use the fact that if \(p\) is a factor of \(N\), then \(N/p\) is also a factor of \(N\). We can prove that \(min(p, N/p) \le \sqrt{N}\). This gives us an \(O(\sqrt{N})\) algorithm to find all the factors of \(N\).

Pseudocode

def divisor_count(N):
    divisors = 0
    i = 1
    while i * i <= N:
        if N % i == 0:
            p = i
            q = N / i
            divisors += 1
            if p != q:
                # Handle the case when N is not perfect square.
                divisors += 1

        i += 1
    
    return divisors

Moving towards prime factorization

An alternate way of counting divisors is to decompose \(N\) into it’s prime factors \(\{p_1, p_2, … p_k\}\) such that \(N = p_1^{c_1} \cdot p_2^{c_2} \cdot \ldots \cdot p_k^{c_k}\). Now the number of divisors of \(N\) is simply \(d(N) = (a_1 + 1)(a_2 + 1)\ldots(a_k + 1)\), where \(d(N)\) denotes the number of divisors of \(N\). One important thing to note about \(d(N)\) is that if \(P \cdot Q = N\) and \(gcd(P, Q) = 1\), then \(d(N) = d(P) \cdot d(Q)\). The proof is left as an exercise for the reader.

Similar to the naive approach, we can loop over primes \(p_i\) such that \(p_i \le \sqrt{N}\) and find corresponding \(a_i\). The number left after dividing \(N\) by \(\prod_{i=1}^{k} p_i^{c_i}\) is either 1 or a prime number. The proof is simple – there is only 1 prime \(p \gt \sqrt{N}\) that can divide \(N\).

Pseudocode

def divisor_count(N):
    primes = list of primes <= sqrt(N)
    product = 1
    for p in primes:
        counter = 0
        while N % p == 0:
            N /= p
            counter += 1
        product *= (counter + 1)
    
    if N != 1:
        product *= 2
    return product

Optimized Solution

Let us try to extend what we have already seen so far. Let’s try to write \(N = X \cdot Y\) such that \(X = \prod_{p_i \le N^{1/3}} p_i^{c_i}\). Finding \(d(X)\) is fairly simple – we only need to consider primes under \(N^{1/3}\). We can also observe that \(gcd(X, Y) = 1\). So if we can find \(d(Y)\), then \(d(N) = d(X) \cdot d(Y)\).

An important observation is that since the minimum number that divides \(Y\) is greater than \(N^{1/3}\), hence we can conclude that \(Y\) has at most 2 prime divisors. Therefore, the possible 4 cases are:

  1. \(Y = 1\), \(d(Y) = 1\)
  2. \(Y\) is a prime number, \(d(Y) = 2\)
  3. \(Y\) is square of a prime number, \(d(Y) = 3\)
  4. \(Y\) is product of 2 prime numbers, \(d(Y) = 4\)

Checking for (1) is simple. If we can check for (2) and (3), then we need not worry about (4). And the common part for both (2) and (3) is primality testing. Let’s write out some pseudocode so we understand the theory until now.

Pseudocode

def divisor_count(N):
    primes = list of primes <= cube root of N
    divisors = 1
    for p in primes:
        counter = 0
        while N % p == 0:
            N /= p
            counter += 1
        divisors *= (counter + 1)

    if is_prime(N):
        divisors *= 2
    elif is_square(N) and is_prime(sqrt(N)):
        divisors *= 3
    elif N != 1:
        divisors *= 4
    return divisors

Implementing is_prime function

The only non trivial part of the above pseudocode is the is_prime function, since the largest prime can be of the order \(O(N)\). We can use a probabilistic primality test – Miller Rabin test. It has a time complexity of \(O(K \cdot log^{3} N)\), where \(N\) is the number tested for primality, and \(K\) is the number of rounds performed.

Analysis

The time complexity of this approach is \(O(N^{1/3} + K \cdot log^{3} N)\). \(K = 20\) is generally sufficient for the Miller Rabin test, hence the overall time complexity is \(O(N^{1/3})\).

Practice

You can try this technique on problems with more lenient requirements as well (eg: for problems requiring \(\sqrt{N}\) factorisation), but here’s one that requires this trick:

Hope you found this useful and happy coding!