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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.