# How to improve this functional python trial division routine?

The following functional program factors an integer by trial division. I am not interested in improving the efficiency (but not in decreasing it either), I am interested how it can be made better or neater using functional constructions. I just seem to think there are a few tweaks to make this pattern more consistent and tight (this is hard to describe), without turning it into boilerplate.

def primes(limit):
return (x for x in xrange(2,limit+1) if len(factorization(x)) == 1)

def factor(factors,p):
n = factors.pop()
while n % p == 0:
n /= p
factors += [p]
return factors+[n] if n > 1 else factors

def factorization(n):
from math import sqrt
return reduce(factor,primes(int(sqrt(n))),[n])


For example, factorization(1100) yields:

[2,2,5,5,11]


It would be great if it could all fit on one line or into two functions that looked a lot tighter -- I'm sure there must be some way, but I can not see it yet. What can be done?

• so factorization is the function you want out of this? because you don't need primes to get it (note also that factorization calls primes and primes calls factorization, that does not look good). Feb 1, 2013 at 8:44
• Why would that not be good? I thought it looked cool. Please explain. Feb 1, 2013 at 8:54

A functional recursive implementation:

def factorization(num, start=2):
candidates = xrange(start, int(sqrt(num)) + 1)
factor = next((x for x in candidates if num % x == 0), None)
return ([factor] + factorization(num / factor, factor) if factor else [num])

print factorization(1100)
#=> [2, 2, 5, 5, 11]


Check this.

• Cool thanks. But I dislike recursion because of stack overflows or max recursion depth. I will try to understand your code though! Feb 1, 2013 at 8:54
• I like get_cardinal_name ! Feb 1, 2013 at 8:55
• Note that the function only calls itself for factors of a number, not for every n being tested, so you'll need a number with thousands of factor to reach the limit. Anyway, since you are learning on Python and functional programming, a hint: 1) lists (arrays) don't play nice with functional programming. 2) not having tail-recursion hinders functional approaches. Feb 1, 2013 at 9:09
• Okay, cool tips about those things. Thanks. I will try to understand this better! Feb 1, 2013 at 9:23