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

• Matt Eckert: Your code finds prime factors, but since the problem requires that the "product of the list equals n," a full prime factorization is necessary. For example, f(100) should return [2, 2, 5, 5] and not [2, 5].
• Prasanth S: Yeah. sorry about this. Will edit shortly.
• Prasanth S: Yeah, just found list comprehensions in docs.python.org/2/howto/functional.html Will modify codes appropriately.
• Prasanth S: @mteckert This is a comment on your solution - not enough reputation to comment directly. 1) Although primes need not be computed to get the correct answer, computing them and running over them alone will be faster. 2) If given the input p^q where p is a large prime, each recursive call will run from 2 to p. This can be avoided by using an auxiliary function that takes the number to start checking from as input, i.e., instead of (x for x in range(2, ceil(sqrt(n))+1) if n%x == 0) you can use (x for x in range(s, ceil(sqrt(n))+1) if n%x == 0) where s is an input to the aux. function.
• Matt Eckert: While there are many ways to optimize the code the focus is on making it more functional, not more performant.