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