Count the number of numbers in a range "A to B" which have the number of divisors equal to N

Question

I am looking for an efficient algorithm to find the number of divisors for all numbers in a huge range up to $10^9$.

Such a task is presented in these two problems: NDIV, and spoj NFACTOR

I used prime factorization to find the number of divisors for each number in the specified range using the following c++ code:

#include <iostream>
using namespace std;

int fact(int x) {
    int sum = 0;
    for (int i = 0, ln = prime.size(); i < ln && prime[i] * prime[i] <= x;
            ++i) {
        for (sum += (x % prime[i] == 0); x % prime[i] == 0; x /= prime[i])
            ;
        if (sum > 10)
            return 11;
    }
    sum += (x > 1);
    return sum;
}

int main() {
    // your code goes here
    return 0;
}

Where "prime" is an array with all prime numbers up to $10^9$, calculated using Sieve of Eratosthenes algorithm.

Answer 1

Are you familiar with the divisor function? If $n=p^aq^br^c, p,q,r$ prime, the number of factors of $n$ is $(a+1)(b+1)(c+1)$ This works for any number of prime factors.

Now take your $N$ and factor it. You can find the patterns of factors that will work. For example, if $N=8$, you can have numbers of the form $p^7,p^3q,$ or $pqr$. The seventh powers are easy to check. For $p^3q$ I would go through the cubes of primes and for each compute the range of $q$ that works, then compute the number of primes in that range. $pqr$ will be the slow one. We can assume $p \lt q \lt r$ but you still have a double loop over primes before finding the range of $r$ that works.

Answer 2

So your question is not: "Given an integer x ≥ 1, how many divisors does x have". Your question is: "Given an integer n ≥ 1, and two integers A ≤ B, how many integers x, A ≤ x ≤ B, have exactly n divisors".

The trivial but inefficient solution is calculating the number of divisors of each x in that range.

A better but still inefficient solution will not calculate the number of divisors of each x in that range, but check that x has n divisors: For example, if n = 2, and x is an even number, then there is no need to calculate the number of divisors: An even x has n = 2 divisors if and only if x = 2. That check will sometimes be hard, sometimes easy.

What you really want is to calculate directly how many integers x have n divisors. As others wrote, for example if $x=p^aq^br^c, p,q,r$ prime, the number of factors of $x$ is $(a+1)(b+1)(c+1)$. This is supposed to be equal to n. So first you find all possible ways to write n as a product of integers ≥ 2. Each such product corresponds to a way to write x as the product of primes.

As an example, let n = 8 = 4 * 2 = 2 * 2 * 2. We see that an integer x with exactly 8 divisors has the form $p^7$, $p^3q^1$, or $p^1q^1r^1$ for primes p, q and r. These can be counted reasonably efficiently: You would count the primes p such that A ≤ $p^7$ ≤ B. Then for every prime p with $2p^3 ≤ B$, you count the primes q such $A ≤ p^3q ≤ B$. Then for every prime p with $p^3 ≤ B$, and for every prime q > p with $pq^2 ≤ B$, count the primes r > q with $A ≤ pqr ≤ B$. In this particular case n = 8 a sieve of all primes up to $B / 6$ would make the counting quite fast. (Why $B/6$ ? Because you need to count among other things the numbers 6r, for 6r ≤ B or r ≤ B/6).