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). –  tokland Feb 1 '13 at 8:44
Why would that not be good? I thought it looked cool. Please explain. –  Cris Stringfellow Feb 1 '13 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! –  Cris Stringfellow Feb 1 '13 at 8:54
I like get_cardinal_name ! –  Cris Stringfellow Feb 1 '13 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. –  tokland Feb 1 '13 at 9:09
Okay, cool tips about those things. Thanks. I will try to understand this better! –  Cris Stringfellow Feb 1 '13 at 9:23