## Sum Of Number of Divisors

Moderator: Board moderators

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

### Sum Of Number of Divisors

Can anyone tell me how the code below works? I mean what's the theory behind it. Or does it really work? I tried it for some values and it gave the right answers.
It's supposed to return the sum of number of divisors of numbers from 1 to N. If you have better approach than this then please let me know.
I really don't understand it. Why stop at the square root and why, after that, double the result then subtract the square of the square root?

Code: Select all

``````long long summation_of_divs_count(long long n)
{
long long sum = 0, root = sqrt(double(n));

for (int i = 1; i <= root; ++i)
sum += (n / i);

return ((sum + sum) - (root * root));
}
``````
EDIT: At last I've found the explanation at http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4204.pdf. Start reading at page 159 if you're also looking for the explanation. Btw, the sequence of the values produced by the function above can also be found at oeis.org. It is sequence no. A006218. The formula above is also written there.
Last edited by oja on Mon Nov 23, 2015 4:29 am, edited 1 time in total.

DGBHS
New poster
Posts: 7
Joined: Tue May 26, 2015 11:58 am

### Re: Sum Of Number of Divisors

Its totally wrong !
solution is
for(1to sqrt(n)-1)
if(n%i==0)
sum=sum+i+n/i;
if(n is perfect square)
sum=sum+sqrt(n)

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

### Re: Sum Of Number of Divisors

You seem to have misunderstood. Your code seems to calculate the sum of divisors of a number. That's not what I meant.
In short, what I want is the summation of the number of divisors of numbers 1 to n.
These are sample values:

1 - 1 (1 has only 1 divisor)
2 - 3 (2 has 2 divisors, so 1 + 2 = 3 )
3 - 5 (3 has 2 divisors, so 3 + 2 = 5 )
4 - 8 (4 has 3 divisors, so 5 + 3 = 8 )