Sum of divisors of numbers of the range ~ 10^6

mathnumbersoptimization

I was trying to find the sum of divisors of numbers upto 106. The test cases are like of the order of 105. I have done some pre processing like 

int divisors(int num)
{
    int sum=0;
    for(int i=1; i*i<=num; i++)
        sum += (num%i)? 0 : ((i*i==num)? i : i+num/i);
    return sum;
}

Is there any better method to do the same. Should I also make an array of prime numbers or something like that?

Best Answer

Hint. It is easier to figure out how many numbers in a range that, say, 12 will divide than it is to bother figuring out which ones it divides.

This gives you a O(n) algorithm that allow you to calculate your answer in likely acceptable time for 106.

If you want it faster, hint 2 is that you only have to do this up to n/2 - after that you just need the sum of the numbers, because each is a factor only once. There is a well-known formula for the sum of all of the integers up to 'n', that provides a short circuit. Still O(n), but a better factor.

For faster still, hint 3 is that you only have to do this up to n/3 - you have 2x the sum of the range from n/3 to n/2 and then all of the range from n/2 to n. Same performance comment as before.

Hint 4 is that as you repeat this there is a more general pattern you can figure out. Get it right and performance becomes O(sqrt(n)) which is definitely fast enough.

Related Topic