Functional prime factor generator I have this prime factor generator for some number n. It returns list of all prime factors. In other words, product of the list equals n.

def prime_factors_generate(n):
    a = []
    prime_list = sorted(primes())
    pindex = 0
    p = prime_list[pindex]
    num = n
    while p != num:
        if num % p == 0:
            a.append(p)
            num //= p
        else:
            pindex += 1
            p = prime_list[pindex]
    return a


The primes() function uses the Sundaram Sieve from here and returns a set of all primes below some limit, by default 106.

How can I make this code functional? I want to get rid of the while-loop, list appending and mutated state.
The implementation of sundaram's sieve that you've mentioned returns primes in sorted order. So, sorted() is not needed.

Also, it is best to define prime_list = primes() outside the definition of prime_factors_generate (This will reduce calls to primes()). You can argue that that will make the code less functional but that would be nitpicking [Even the definition of primes() isn't functional]



EDIT: As pointed out in a comment by mteckert, my earlier solution will not provide the desired result. This EDIT will work though (It'll return [2, 2, 2, 3] instead of [2, 3] for prime_factors_generate(24))

def max_pow(n, x):
    if n%x == 0:
        return max_pow(n/x, x)+1
    else:
        return 0

def prime_factors_generate(n): #Variables added just for convenience. Can be removed.
    prime_list = primes()
    nested_ans = map(lambda x: [x]*max_pow(n, x), prime_list)
    ans = [item for sublist in nested_ans for item in sublist]
    return ans


One liners (if you're interested in them) for max_pow and prime_factors generator:

max_pow = lambda n, x: max_pow(n/x, x)+1 if n%x==0 else 0
prime_factors_generate = lambda n: [item for sublist in map(lambda x: [x]*max_pow(n, x), primes()) for item in sublist]


End of EDIT. I'm leaving my earlier solution intact (which returns [2, 3] for prime_factors_generate(24)).



This should work:

def prime_factors_generate(n): #Variables added just for convenience. Can be removed.
    prime_list = primes()
    prime_factors = filter(lambda x: n % x == 0, prime_list)
    return prime_factors


Or if you're into one liners:

prime_factors_generate = lambda n: filter(lambda x: n % x == 0, primes())