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

但是我这里有3个可怕的for循环。是否可以将其抽象成一个函数，并给定任何分解为字典对象参数的因子？

- Christwo

---

我的数学有些生疏，什么原理可以让你从质因数推导出所有的因数？ - Mark Roddy

这可能源于算术基本定理，因为任何非质因数都有唯一的质因数分解，而这些质因数分解包含在较大数的质因数分解中。 - user57368

这个回答解决了你的问题吗？快速素因子分解模块 - undefined

Answer 1

我已经在博客中写过这个问题，最快的纯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}。

- Jaime

---

哇，这速度真是惊人！ - Christwo

真的很快...我花了一些时间试图赋予它“个人化的感觉”，最终得出的结论是，即使重命名变量也会对速度产生负面影响！！！;-) - Jaime

Answer 2

使用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]

- jfs

---

你需要使用 operator.mul，而不是 operator.prod :) - Nicolas Dumazet

这确实很好，但我不喜欢它依赖于Python 2.6中的一些新函数。 - Christwo

@Christwo：itertools.product的文档（请参见我提供的链接）包含product()的纯Python实现。只有6行代码。 - jfs

Answer 3

好的，不仅你有3个循环，而且如果你有超过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

- Nicolas Dumazet

---

+1，这是一个比较好的解决方案，因为它展示了通过将乘积与每个新集合相乘来获取[r_0]和[r_1]的笛卡尔积。 - Edmund

Answer 4

是的。当您有一个需要n个嵌套for循环的算法时，通常可以将其转换为递归函数：

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)

- Edmund

---

eeek. O(nfactorfactordepth) 调用：O(nfactorfactordepth) 字典？:( - Nicolas Dumazet

是的，我有一个版本，但它更丑陋，而且在展示递归循环的基本思想方面不够有效。 - Edmund

Answer 5

基本上，您在这里拥有的是一个集合，由目标数字的每个因子组成。在您的示例中，该集合将为{2 2 2 3 3 5}。该集合的每个严格子集都是您数字的一个因数的分解，因此如果您可以生成该集合的所有子集，则可以将每个子集的元素相乘并获得所有整数因子。

从那里开始，代码应该很明显：生成一个包含因式分解的列表，生成该列表的所有子集（使用生成器获得奖励；我认为标准库中有一个相关函数）。然后进行乘法并继续进行。虽然不是最优效率，但看起来很好。

- David Seiler