0

I have to find sum of proper divisor upto N (N <= 20000000). I have pre-calculate this function with complexity O(N * log(N)) which takes upto 4 second. How can I optimize it or any alternate solution will be greatly accepted.

Example: N = 10 answer is 86, N = 1000 answer is 823080

int f(){
   for(LL i = 1; i <= m; i++){
       for(LL j = i; j <= m; j += i){
           ans[j] += i;
       }
   }
   for(LL i = 2; i <= m; i++)     ans[i] += ans[i - 1];
}

I also tried using prime factorization and this formula, but it takes more time than above algorithm.

Jobayer sheikh
  • 27
  • 3
  • 13
  • This question has already been answered very well at: http://stackoverflow.com/questions/7323572/how-to-find-total-number-of-divisors-upto-n/8337647#8337647 – emilio May 05 '16 at 15:27

1 Answers1

0

I can't edit my previous comment, only to say that the problem referenced by my comment is a little bit different, but with a minor adjustment it answers also this question. Just multiply inside the loop by the divisor itself.

emilio
  • 71
  • 1
  • 9