Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.