1
\$\begingroup\$

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?

\$\endgroup\$
2
  • \$\begingroup\$ 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). \$\endgroup\$
    – tokland
    Feb 1, 2013 at 8:44
  • \$\begingroup\$ Why would that not be good? I thought it looked cool. Please explain. \$\endgroup\$ Feb 1, 2013 at 8:54

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Cool thanks. But I dislike recursion because of stack overflows or max recursion depth. I will try to understand your code though! \$\endgroup\$ Feb 1, 2013 at 8:54
  • \$\begingroup\$ I like get_cardinal_name ! \$\endgroup\$ Feb 1, 2013 at 8:55
  • \$\begingroup\$ 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. \$\endgroup\$
    – tokland
    Feb 1, 2013 at 9:09
  • \$\begingroup\$ Okay, cool tips about those things. Thanks. I will try to understand this better! \$\endgroup\$ Feb 1, 2013 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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