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):)
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.