Python因数分解

Question

我想知道，如何最好地列出一个数字的所有整数因子，前提是我有一个字典，里面包含它的质因数和对应的指数。
比如说，如果我们有 {2:3, 3:2, 5:1} (也就是 2 的 3 次方乘以 3 的 2 次方再乘以 5，结果是 360)
那么我可以这样写：

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

但是这里我用了三个很麻烦的循环。有没有办法把这个过程抽象成一个函数，能够接受任何因式分解的字典作为参数呢？

Answer 1

使用Python 2.6中的itertools.product：

#!/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)

示例：

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

输出：

[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 2

我在博客上写过这个，最快的纯Python（不使用itertools）的方法来自Tim Peters在Python邮件列表上的一篇帖子，使用了嵌套的递归生成器：

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

需要注意的是，这段代码是以列表的形式来处理质因数，而不是字典，也就是说，它接受的是像[2, 2, 2, 3, 3, 5]这样的列表，而不是像{2 : 3, 3 : 2, 5 : 1}这样的字典。

Answer 3

其实，你不仅有三个循环，而且如果你有超过三个的因素，这种方法就不太管用了 :)

这里有一种可能的做法：

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

另外，你可以避免在内层循环中重复一些工作：假设你的工作集是 (1,3)，想要应用到 2^3 的因素，我们之前做的是：

• (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)

你能看到第二组中有多少重复的元素吗？

但我们可以这样做：

• (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)

这样解决方案看起来更简洁，没有使用集合：

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