Python factorization

Question

I'd just like to know the best way of listing all integer factors of a number, given a dictionary of its prime factors and their exponents.
For example if we have {2:3, 3:2, 5:1} (2^3 * 3^2 * 5 = 360)
Then I could write:

for i in range(4):
  for j in range(3):
    for k in range(1):
      print 2**i * 3**j * 5**k

But here I've got 3 horrible for loops. Is it possible to abstract this into a function given any factorization as a dictionary object argument?

Answer 1

I have blogged about this, and the fastest pure python (without itertools) comes from a post by Tim Peters to the python list, and uses nested recursive generators:

def divisors(factors) :
    """
    Generates all divisors, unordered, from the prime factorization.
    """
    ps = sorted(set(factors))
    omega = len(ps)

    def rec_gen(n = 0) :
        if n == omega :
            yield 1
        else :
            pows = [1]
            for j in xrange(factors.count(ps[n])) :
                pows += [pows[-1] * ps[n]]
            for q in rec_gen(n + 1) :
                for p in pows :
                    yield p * q

    for p in rec_gen() :
        yield p

Note that the way it is written, it takes a list of prime factors, not a dictionary, i.e. [2, 2, 2, 3, 3, 5] instead of {2 : 3, 3 : 2, 5 : 1}.

Answer 2

Well, not only you have 3 loops, but this approach won't work if you have more than 3 factors :)

One possible way:

def genfactors(fdict):    
    factors = set([1])

    for factor, count in fdict.iteritems():
        for ignore in range(count):
            factors.update([n*factor for n in factors])
            # that line could also be:
            # factors.update(map(lambda e: e*factor, factors))

    return factors

factors = {2:3, 3:2, 5:1}

for factor in genfactors(factors):
    print factor

Also, you can avoid duplicating some work in the inner loop: if your working set is (1,3), and want to apply to 2^3 factors, we were doing:

• (1,3) U (1,3)*2 = (1,2,3,6)
• (1,2,3,6) U (1,2,3,6)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) U (1,2,3,4,6,12)*2 = (1,2,3,4,6,8,12,24)

See how many duplicates we have in the second sets?

But we can do instead:

• (1,3) + (1,3)*2 = (1,2,3,6)
• (1,2,3,6) + ((1,3)*2)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) + (((1,3)*2)*2)*2 = (1,2,3,4,6,8,12,24)

The solution looks even nicer without the sets:

def genfactors(fdict):
    factors = [1]

    for factor, count in fdict.iteritems():
        newfactors = factors
        for ignore in range(count):
            newfactors = map(lambda e: e*factor, newfactors)
            factors += newfactors

    return factors

Answer 3

Using itertools.product from Python 2.6:

#!/usr/bin/env python
import itertools, operator

def all_factors(prime_dict):
    series = [[p**e for e in range(maxe+1)] for p, maxe in prime_dict.items()]
    for multipliers in itertools.product(*series):
        yield reduce(operator.mul, multipliers)

Example:

print sorted(all_factors({2:3, 3:2, 5:1}))

Output:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60,
 72, 90, 120, 180, 360]

Answer 4

Yes. When you've got an algorithm that needs n nested for loops, you can usually turn it into a recursive function:

def print_factors(d, product=1):
    if len(d) == 0:      # Base case: we've dealt with all prime factors, so
        print product    # Just print the product
        return
    d2 = dict(d)         # Copy the dict because we don't want to modify it
    k,v = d2.popitem()   # Pick any k**v pair from it
    for i in range(v+1): # For all possible powers i of k from 0 to v (inclusive)
                         # Multiply the product by k**i and recurse.
        print_factors(d2, product*k**i)

d = {2:3, 3:2, 5:1}
print_factors(d)

Answer 5

Basically, what you have here is a set, consisting of each factor of the target number. In your example, the set would be {2 2 2 3 3 5}. Each strict subset of that set is the factorization of one of the divisors of your number, so if you can generate all the subsets of that set, you can multiply the elements of each subset together and get all the integer divisors.

The code should be pretty obvious from there: generate a list containing the factorization, generate all subsets of that list (bonus points for using a generator; I think there's a relevant function in the standard library). Then multiply and go from there. Not optimally efficient by any means, but nice looking.