Prime factorization code

gistfile1.py

import math

def memoize(f):
    memo = {}
    def wrapper(val):
        if val not in memo:
            memo[val] = f(val)
        return memo[val]
    return wrapper

def unify_factors(a, b):
    final = dict()
    for (prime, factor) in a:
        if prime not in final: final[prime] = 0
        final[prime] += factor
    for (prime, factor) in b:
        if prime not in final: final[prime] = 0
        final[prime] += factor
    return final.items()

@memoize
def factorize(x):
    lim = math.ceil(math.sqrt(x))
    for i in xrange(2,int(lim) + 1):
        if i == x: continue
        if x % i != 0: continue
        mul_a = i
        mul_b = x / i
        assert mul_a * mul_b == x
        return unify_factors(factorize(mul_a), factorize(mul_b))
    # x is prime
    return [(x, 1)]

def render(factorization):
    factors = []
    for (prime, factor) in factorization:
        factors.append(u"%s^{%s}"% (prime, factor))
    return u"$" + u"".join(factors) + u"$"

all_factors = []
for i in xrange(2,100+1):
    facts = list(sorted(factorize(i)))
    print u"{0} & {1} \\\\".format(i, render(facts)).encode("utf-8")
    all_factors.append(facts)

# 100! factors:
_100f_factors = reduce(unify_factors, all_factors)
print u"100! = {0}".format(render(_100f_factors))