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.