Iteration over recursion?

[Kay Schluehr]

You might use a separate prime generator to produce prime factors. The
factorize algorithm becomes quite simple and configurable by prime
generators. For demonstration purposes I use the eratosthenes sieve.

def eratosthenes():
    memo = {}
    q = 2
    while True:
        p = memo.pop(q, None)
        if p is None:
            yield q
            memo[q*q] = q
        else:
            x = p + q
            while x in memo:
                x += p
            memo[x] = p
        q+=1

def factorize(n, sieve = eratosthenes):
    if n <= 1:
        return [n]
    factors = []
    primes = sieve()
    for q in primes:
        while n % q == 0:
            factors.append(q)
            n //= q
            if n == 1:
                return factors

Regards,
Kay