hereicomewf's blog

Interesting Math Problem...
By hereicomewf, 10 years ago, In English

I was trying to solve This Problem on Spoj.

The problem is to find the sum of all divisors of i where i=1 to i=N.

We have to solve this in sqrt(n) complexity.

This is the Ac'ed python Code, I couldn't figure out the logic behind this.

Please provide me with some hints..Thanks

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Let .

For each x = 1..m we can find count of numbers divisible by x. It's

For each k = 1..m - 1 we can find all numbers x that divide exactly k numbers. It's range

→ Reply