Functional prime factor generator

Question

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 10⁶.

How can I make this code functional? I want to get rid of the while-loop, list appending and mutated state.

Answer 1

There are a few things you can do to make your code more functional. First note that it isn't necessary to have a list of primes beforehand. As you eliminate factors from the bottom up, there cannot be a composite "false positive" since its prime factors will have been accounted for already.

Here is a more functional version of your code:

from math import ceil, sqrt

def factor(n):
    if n <= 1: return []
    prime = next((x for x in range(2, ceil(sqrt(n))+1) if n%x == 0), n)
    return [prime] + factor(n//prime)

Generator expression

This is a generator expression, which is a generator version of list comprehensions:

(x for x in range(2, ceil(sqrt(n))+1) if n%x == 0)

Note that in Python 2.7.3, ceil returns a float and range accepts ints.

Basically, for every number from 2 to ceil(sqrt(n)), it generates all numbers for which n%x == 0 is true. The call to next gets the first such number. If there are no valid numbers left in the expression, next returns n.

Recursion

This is a recursive call, that appends to our list the results of nested calls:

return [prime] + factor(n//prime)

For example, consider factor(100). Note that this is just a simplification of the call stack.

The first prime will be 2, so:

return [2] + factor(100//2)

Then when the first recursive call is to this point, we have:

return [2] + [2] + factor(50//2)
return [2] + [2] + [5] + factor(25//5)
return [2] + [2] + [5] + [5] + factor(5//5)

When factor is called with an argument of 1, it breaks the recursion and returns an empty list, at if n <= 1: return []. This is called a base case, a construct vital to functional programming and mathematics in general. So finally, we have:

return [2] + [2] + [5] + [5] + []
[2, 2, 5, 5]

Generator version

We can create a generator version of this ourselves like this:

from math import ceil, sqrt

def factorgen(n):
    if n <= 1: return
    prime = next((x for x in range(2, ceil(sqrt(n))+1) if n%x == 0), n)
    yield prime
    yield from factorgen(n//prime)

The keyword yield freezes the state of the generator, until next is called to grab a value. The yield from is just syntactic sugar for

for p in factorgen(n//prime):
    yield p

which was introduced in Python 3.3.

With this version, we can use a for loop, convert to a list, call next, etc. Generators provide lazy evaluation, another important tool in a functional programmer's arsenal. This allows you to create the "idea" for a sequence of values without having to bring it into existence all at once, so to speak.

Though I didn't use it here, I can't resist mentioning a very nice Python library named itertools, which can help you immensely with functional-style programming.

Answer 2

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