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.
Best Answer
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).