素因数分解を高速にやるには

こんなコードを書いたけど、n以下の素数のリストを得ずに、例えば素数テストを使ってもっと早く計算できたりするのかなぁ。

# coding: utf-8
import primetable

def factory(n = 10**7):
    ps = primetable.primelist(n) # n以下の素数をリストで返す
    memo = {1: []}
    for p in ps:
        memo[p] = [p]
    def primefactorization(n):
        if n in memo:
            return memo[n]
        for p in ps:
            if n % p == 0:
                pf = primefactorization(n / p)
                memo[n] = pf + [p] #([p] if p not in pf else [])
                return memo[n]
    return primefactorization
#
# factorizer = factory(100)
# factorizer(10) # => [5, 5, 2, 2]
# factorizer(31) # => [31]
#