我有一个数字的质因数的Python列表。如何（用Python方式）找到所有因数？

Question

我正在做一个Project Euler的问题，需要对一个整数进行因数分解。我可以列出所有是某个数字因子的质数。算术基本定理告诉我们，我可以利用这个质数列表来推导出这个数字的所有因数。

我现在的计划是，拿这个质数列表中的每个数字，把它的幂次提高，直到它不再是整数因数，这样我就能找到每个质数的最大指数。然后，我会把所有可能的质数和指数的组合相乘。

举个例子，对于180：

Given: prime factors of 180: [2, 3, 5]
Find maximum exponent of each  factor: 
    180 / 2^1 = 90
    180 / 2^2 = 45
    180 / 2^3 = 22.5 - not an integer, so 2 is the maximum exponent of 2.

    180 / 3^1 = 60
    180 / 3^2 = 20
    180 / 3^3 = 6.6 - not an integer, so 2 is the maximum exponent of 3.

    180 / 5^1 = 36
    180 / 5^2 = 7.2 - not an integer, so 1 is the maximum exponent of 5.

接下来，做这些组合，直到达到最大指数，以得到因数：

    2^0 * 3^0 * 5^0 = 1
    2^1 * 3^0 * 5^0 = 2
    2^2 * 3^0 * 5^0 = 4
    2^0 * 3^1 * 5^0 = 3
    2^1 * 3^1 * 5^0 = 6
    2^2 * 3^1 * 5^0 = 12
    2^0 * 3^2 * 5^0 = 9
    2^1 * 3^2 * 5^0 = 18
    2^2 * 3^2 * 5^0 = 36
    2^0 * 3^0 * 5^1 = 5
    2^1 * 3^0 * 5^1 = 10
    2^2 * 3^0 * 5^1 = 20
    2^0 * 3^1 * 5^1 = 15
    2^1 * 3^1 * 5^1 = 30
    2^2 * 3^1 * 5^1 = 60
    2^0 * 3^2 * 5^1 = 45
    2^1 * 3^2 * 5^1 = 90
    2^2 * 3^2 * 5^1 = 180

所以因数列表 = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

这是我目前写的代码。有两个问题：首先，我觉得这段代码一点也不“Pythonic”（就是不够符合Python的风格）。我想改进这一点。其次，我真的没有找到一个Pythonic的方法来处理组合的第二步。为了避免尴尬，我就不把那些复杂的循环给你们看了。

n是我们想要分解的数字，listOfAllPrimes是一个预先计算好的质数列表，范围到1000万。

def getListOfFactors(n, listOfAllPrimes):
    maxFactor = int(math.sqrt(n)) + 1
    eligiblePrimes = filter(lambda x: x <= maxFactor, listOfAllPrimes)
    listOfBasePrimes = filter(lambda x: n % x ==0, eligiblePrimes)

    listOfExponents = [] #(do I have to do this?)
    for x in listOfBasePrimes:
        y = 1
        while (x**(y+1)) % n == 0:
            y += 1
        listOfExponents.append(y)

Answer 1

你可以使用 itertools.combinations() 来获取所有可能的因子组合。比如说，当你得到了重复质数的列表，比如 [2, 2, 3, 3, 5] 代表数字 180 时。然后，只需把每个组合中的元素相乘，就能得到一个因子。

Answer 2

你为什么从质因数开始解决问题呢？当你对一个数字进行因式分解时，其实可以很容易地得到所有的质因数（包括重复的），然后从这些质因数中得到每个因数的指数。考虑到这一点，你可以这样写：

import itertools
prime_factors = get_prime_factors(180) 
# 2, 2, 3, 3, 5 
factorization = [(f, len(list(fs))) for (f, fs) in itertools.groupby(prime_factors)]
# [(2, 2), (3, 2), (5, 1)]
values = [[(factor**e) for e in range(exp+1)] for (factor, exp) in factorization]
# [[1, 2, 4], [1, 3, 9], [1, 5]]
print sorted(product(xs) for xs in itertools.product(*values))
# [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

get_prime_factors 和 product 这里没有实现，但你明白我的意思（这两个函数其实都很简单）。

在我看来，这些问题属于数学问题，欧拉问题可以用函数式编程的方式很好地解决，而不是用命令式编程（不过我承认，有些解决方案可能没有那么符合 Python 的风格）。

Answer 3

与其列出指数，不如直接把每个质因数重复出现，重复的次数就是它作为因数的次数。接下来，处理这个包含重复的质因数列表，使用itertools.combinations就能满足你的需求——你只需要组合长度在2到len(primefactors) - 1之间的项（组合长度为1的就是质因数，组合长度为所有的则是原始数字——如果你也想要这些，可以用range(1, len(primefactors) + 1)，而不是我主要建议的range(2, len(primefactors))）。

结果中会有重复的项（比如6会作为12的因数出现两次，因为12的质因数是[2, 2, 3]），当然可以用常见的方法去掉这些重复项（例如用sorted(set(results))）。

要计算primefactors，给定listOfAllPrimes，可以考虑以下示例：

def getprimefactors(n):
    primefactors = []
    primeind = 0
    p = listOfAllPrimes[primeind]
    while p <= n:
        if n % p == 0:
            primefactors.append(p)
            n //= p
        else:
            primeind += 1
            p = listOfAllPrimes[primeind]
    return primefactors