Vectorrr's blog

Sum of divisors of a number
By Vectorrr, history, 8 years ago, In English

Hello everyone, I was trying to solve this problem but i couldnt handle it, could someone please help me? Given n 1 <= n <= 10^9 we have to find if there is a number which sum of divisors (including that number as a divisor) is equal to n and print it otherwise we have to print -1.

For example Input : 7; Output : 4, Since 7 = 4 + 2 + 1 Input : 1767 Output : 1225 Since 1767 = 1 + 5 + 7 + 25 + 35 + 49 + 175 + 245 + 1225

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't get it :/

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

if x = p1k1p2k2... pmkm

then sum of divisors of x equal to (1 + p1 + p12 + ... + p1k1)(1 + p2 + p22 + ... + p2k2)... (1 + pm + pm2 + ... + pmkm)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But how to do for n = 109 ? trying every number leads to O(n * log(n)) if prime factorisation done in log(n) . cannot find a pattern to use

    → Reply