# Python, Straightforward with Explanation

• Let's consider the problem of finding the sum of all divisors of N.

Consider the prime factorization of N, for example suppose it was 2^a * 3^b * 5^c... Every divisor is going to be some 2^i 3^j 5^k... for i in [0,a], j in [0,b] etc. The sum of all of these is simply (2^0 + 2^1 + ... + 2^a) * (3^0 + 3^1 + ... + 3^b) * (5^0 + 5^1 + ... + 5^c) * ... .

How might we find the prime factorization of N? This is a standard technique worth learning.

Look at our function prime_factorization, which is defined for positive integers. Our loop invariant is: d will be the least number that N might be divisible by. We'll divide out factors of d and record the number of such divisions as the exponent of d in the prime factorization of N. Since we have checked all numbers before it and divided them out of N, d will always be prime. After checking all potential primes <= sqrt(N), if N > 1 then it must be prime, and we should record that too.

We should also be careful to remember that negative N's are always not perfect.

``````def prime_factorization(N):
d = 2
while d * d <= n:
expo = 0
while N % d == 0:
expo += 1
N /= d
if expo:
yield (d, expo)
d += 1
if N > 1:
yield (N, 1)

ans = 1
for prime, expo in prime_factorization(abs(N)):
ans *= sum(prime ** k for k in xrange(expo + 1))
return ans == 2*N
``````

Note: I try to focus my editorials on the most repeatable and instructive solutions, not the most clever or short.

• (Edit: awice edited his code now, here I was talking about the original version using `for d in xrange(2, int(N**.5) + 1):`)

@awice Your `prime_factorization` does unnecessary work and yields unnecessary values. For example `print list(prime_factorization(216))` prints `[(2, 3), (3, 3), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0), (10, 0), (11, 0), (12, 0), (13, 0), (14, 0)]`. All those factors with exponent zero better shouldn't be yielded or even computed in the first place. Here's a better version which results in only `[(2, 3), (3, 3)]`:

``````def prime_factorization(n):
d = 2
while d * d <= n:
expo = 0
while n % d == 0:
expo += 1
n /= d
if expo:
yield d, expo
d += 1
if n > 1:
yield n, 1
``````

It's not just cleaner but also faster. For the following test, your version takes me about 15.4 seconds while my version takes me about 2.2 seconds (though to be honest, I was hoping/expecting the difference to be larger):

``````from time import time
t0 = time()
for i in xrange(10**8 - 10000, 10**8):
list(prime_factorization(i))
print time() - t0
``````

With a little math knowledge, you also don't need the `sum` over a loop:

``````divsum = 1
for p, e in prime_factorization(num):
divsum *= (p**(e+1) - 1) / (p - 1)
return divsum == 2 * num
``````

Btw, I just posted a short Ruby version using Ruby's own factorization method. I'm always happy when I can use that :-)

• Good catch, I pasted the wrong thing and edited the OP. The function you showed was the same as what I did on the contest.

• @awice Better try it out, your edited version doesn't work.

Edit: Oh, looking at your competition solution I also realized we were missing the `if expo:` here. I added that now and updated the run time (dropped from 3.8 to 2.2 seconds).

Edit 2: Using `d += 1 + (d > 2)` instead of `d += 1` drops the time further, to 1.3 seconds.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.