Python, Straightforward with Explanation


  • 4

    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.


  • 1

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


  • 0

    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.


  • 1

    @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.


Log in to reply
 

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