Sum Of Number of Divisors

Let's talk about algorithms!

Moderator: Board moderators

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

Sum Of Number of Divisors

Post by oja » Fri May 22, 2015 3:52 pm

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

Post by DGBHS » Thu Jul 02, 2015 9:38 pm

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

Post by oja » Wed Jul 08, 2015 10:58 am

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 )

Post Reply

Return to “Algorithms”