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

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?

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.

• I'm having difficulty figuring out if this is part of your conclusion, but in factorization, you only need up to sqrt(n), not n/2 or n/3 or whatever other constant. n/2 for 12 is 6, but sqrt(12) is ~3.46. That means you'll iterate (1,12), (2,6), and (3,4) before hitting ~3.46 and giving up. Meanwhile with 6, you'd do (1,12), (2,6), (3,4), (4,3), (6,2). – Joel Jul 9 '13 at 15:39
• @Joel That is indeed why you get `O(sqrt(n))` though I'm trying to avoid giving full details. The sum of the factors up to and including `sqrt(n)` is calculated one way. The sum of factors larger than `sqrt(n)` is counted another way. Each piece is `O(sqrt(n))`. With `n` at a million, that means you do thousands of operations, rather than millions or - if you try factoring individually, tens of millions or hundreds of millions. These things add up. :-) – btilly Jul 9 '13 at 16:39
• I saw the O(sqrt(n)) but in my head, Big O is about the relative complexity of a series of operations and for some (wrong) reason, I was thinking of using the sqrt function as a different series of operations than linear iteration. Then I realized that the iteration is by far the most significant factor a bit after writing that. It indeed makes sense to phrase it the way you did, it just didn't click for me until after I had thought about it. I'm not sure which is more powerful; giving hints to the answer so the person discovers it or explaining why the answer works. Now the asker has both. :) – Joel Jul 9 '13 at 21:39