Q:

Number of divisors in a range [a,b], a and b can be large numbers

Suppose for finding number of divisors of all numbers between 1 and N, we use:
for (i = 1; i < N; ++i) 
    for (j = i; j < N; j += i) 
        factors[j]++;

What should we do if the range is something like [a,b] such that 1 < a,b < 10^9 and b-a < 10,000?
If we adapt the code above as:
for (i = 1; i < b; ++i)
    for (j = i; j < b; j += i)
        factors[j]++;

it would take too much time to run if b = 10^9. So what kind of optimization can be made, given that b-a is small relative to a and b, and a and b are large (10^9 or more)?
PS. Maybe I couldn't explain the problem well. What I actually need to find is how many numbers in the range have number of divisors equal to some x <= 100. 
Thanks.

A:

The basic answer is to calculate the factorization of each number of interest, then use that to calculate the number of divisors: if the factorization is a^w * b^x * c^y * d^z then the number of divisors is (w+1) * (x+1) * (y+1) * (z+1).
You can find the factorization in a couple of ways. One way is by trial division; since the limit of 10^9 is small, trial division will work without too much pain. Another way is by sieving, using a segmented Sieve of Eratosthenes to find the factors, then calculating their multiplicities by division.
You can find algorithms and code for trial division, the segmented Sieve of Eratosthenes, and calculating the divisors of a number on my blog. Click on Exercises on the menu bar, then Themes, then select Prime Numbers.
EDIT: Here's how I would do it.
The first step is to sieve for the factors of all the numbers in the range. Calculate the primes less than the square root of b using the Sieve of Eratosthenes. Create an array of length b - a + 1 with each element initialized to an empty list. For each prime less than the square root of b calculate the first number k greater than or equal to a that is a multiple of the prime, then for each array element starting at k - a and at intervals of p -- k - a + p, k - a + 2 p, k - a + 3 p, and so on -- add p to the list at the array location. That gives you a list of the factors of all the numbers in the range, but not their multiplicities.
The second step is to calculate the number of divisors of all the numbers in the range. Each element i of the array contains a list. If the list is empty, the number is prime, and the number a + i has two divisors. Otherwise, use trial division by the known factors in the list to determine their multiplicities, and use those multiplicities to calculate the number of divisors.
Then you just count those in the range with a number of divisors equal to x.

