Sum of number of divisor of number between a and b inclusive

Question

Let there be a function g(x)=number of divisor of x. Given two integers a and b we need to find->

g(a)+g(a+1)....+g(b).

I thought this step->

for every x from a to b

sum+=number of divisor of x(in sqrt(x) complexity)

but its given 1<=a<=b<=2^31-1

So to iterate between a and b can cost me a lot of time....for eg->if a=1 and b=2^31-1.

Is there a better way to do?

Answer 1

We can adapt this algorithm: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes by adding 1 to all multiples instead of flagging them as "not prime"

it will be o(n.ln(n)) with a=1 and b=n (i think)

algorithm for 1 to n:

g: array of n elements
for i starting with 2 to n
    if g[i]== 0
        for each multiple of i <n
            g[i] += 1  

Answer 2

Here's some simple but reasonably efficient Python code that does the job.

import math

def T(n):
    "Return sum_{i=1}^n d(i), where d(i) is the number of divisors of i."
    f = int(math.floor(math.sqrt(n)))
    return 2 * sum(n // x for x in range(1, f+1)) - f**2

def count_divisors(a, b):
    "Return sum_{i=a}^b d(i), where d(i) is the number of divisors of i."
    return T(b) - T(a-1)

Explanation: it's enough to be able to compute the sum from 1 to b, then we can do two separate computations and subtract to get the sum from a to b. Finding the sum of the divisor function from 1 to b amounts to computing sequence A006218 from the online encyclopaedia of integer sequences. That sequence is equivalent to the sum of floor(n / d) as d ranges over all integers from 1 to n.

And now that sequence can be thought of as the number of integer-valued points under the hyperbola xy=n. We can use the symmetry of the hyperbola around the line x = y, and count the integer points with x <= sqrt(n) and those with y <= sqrt(n). That ends up double counting the points with both x and y less than sqrt(n), so we subtract the square of floor(sqrt(n)) to compensate. All this is explained (briefly) in the introduction to this paper.

Remarks:

• the algorithm has running time O(sqrt(b)), and constant space requirements. Improvements in running time are possible at the expense of space; see the paper referred to above.

• for really large n, you'll want a proper integer square root rather than using floor(math.sqrt(n)), to avoid problems with floating-point inaccuracies. That's not a problem with the sort of n that you're looking at. With typical IEEE 754 floating-point and a correctly rounded square root operation, you're not going to run into trouble until n exceeds 2**52.

• if a and b are really close, there may be more efficient solutions.

Answer 3

Another sieve-based answer, but with a better time complexity than the others. This one also handles segmentation easily, since it only sieves numbers {a...b} on each run. The function returns an int[] with the number of divisors for each number from a to b. Just sum them up to get the final answer.

If your inputs are larger, you can split it up and add the sums from each returned segment.

Java:

public static int[] getDivisorCount(int a, int b){
    int[] sieve = new int[b - a + 1];
    double max = Math.ceil(Math.sqrt(b));
    for(int i = 1; i <= max; i++){
        int j = (a / i) * i;
        if(j < a)
            j += i;
        for( ; j <= b; j += i){
            double root = Math.sqrt(j);
            if(i < root){
                sieve[j - a] += 2;
            }else if(i == root){
                sieve[j - a]++;
            }
        }
    }
    return sieve;
}

The outer loop runs sqrt(b) times. The inner loop runs something like log(b-a) times, so unless I'm mistaken, the final complexity should be something like O(sqrt(b) * log(b)), since worst case is a=1. Feel free to correct me on that.

If you're handling large inputs and you have the space to spare, you might want to consider prepopulating a sqrt table to get it out of the inner loop. It would speed it up, and if you've got the memory to spare, there's no real down side to it.

For a quick test, here's an ideone.com example.

Edit: If you're looking for a sieve, this is fine. However, I must say that jwpat7's answer is 1)faster, 2) constant space, and 3) more elegant (IMO). There's basically no reason to use a sieve unless you're interested in the mechanics of it.

Answer 4

Because the desired result is the total number of divisors for all the numbers in a range, there's no need to count divisors of individual numbers in the range; instead, count the number of times 1 is a divisor, 2 is a divisor, etc. This is an O(b) computation.

That is, add up b-(a-1), b/2 - (a-1)/2, b/3 - (a-1)/3, etc. .

In the python code shown below (which uses python operator // for integer division with truncation) divisors from 2 to about b/2 are counted using a for loop. Note that divisors that are smaller than b but larger than max(a, b/2) occur once each and need not be counted in a loop. The code uses the expression b-max(a,(b+1)//2+1)+1 to count them. Output is shown after the program.

When k different a,b sets are to be treated, it is possible to compute all the answers in time O(k+bₘₐₓ) where bₘₐₓ is the largest value of b.

Python code:

def countdivisors(a,b):
    mid = (b+1)//2+1
    count = b-a+1 +b-max(a,mid)+1 # Count for d=1 & d=n
    for d in xrange(2,mid):
        count += b//d - (a-1)//d
    return count
# Test it:
a=7
for b in range(a,a+16):
    print '{:3} {:3} : {:5}'.format(a, b, countdivisors(a,b))

Output:

  7   7 :     2
  7   8 :     6
  7   9 :     9
  7  10 :    13
  7  11 :    15
  7  12 :    21
  7  13 :    23
  7  14 :    27
  7  15 :    31
  7  16 :    36
  7  17 :    38
  7  18 :    44
  7  19 :    46
  7  20 :    52
  7  21 :    56
  7  22 :    60

Answer 5

You can sieve for the count of divisors, then sum the counts:

function divCount(a,b)
    num := makeArray(1..b, 0)
    for i from 1 to b
        for j from i to b step i
            num[j] := num[j] + 1
    sum := 0
    for i from a to b
        sum := sum + num[i]
    return sum

This is similar to a Sieve of Eratosthenes, but instead of marking off the composites it counts each divisor for every number, including both primes and composites. If b is too large, you can perform the sieving in segments.