How to improve this functional python trial division routine?

Question

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?

• tokland: 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).
• Cris Stringfellow: Why would that not be good? I thought it looked cool. Please explain.

Answer 1

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.

• Cris Stringfellow: Cool thanks. But I dislike recursion because of stack overflows or max recursion depth. I will try to understand your code though!
• Cris Stringfellow: I like get_cardinal_name !
• tokland: 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.
• Cris Stringfellow: Okay, cool tips about those things. Thanks. I will try to understand this better!