python - 我有一个数字素因数的 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。我想解决这个问题。其次，我真的没有 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

考虑简单地重复每个质因数，而不是指数列表，它是一个因数。之后，处理生成的 primefactors list-with-repetitions，itertools.combinations做你需要的——你只需要长度 2 到 len(primefactors) - 1 项的组合(只有一个的组合是主要因素，所有的组合都会是原始数字——如果你也想要这些，只需使用 range(1, len(primefactors) + 1) 而不是 range(2, len(primefactors)) 我的主要建议是使用哪个)。

结果中会有重复(例如，6 将作为 12 的因数出现两次，因为后者的 primefactors 将是[2, 2, 3])，当然可以用通常的方式将它们剔除(例如 sorted(set(results)))。

要计算给定 listOfAllPrimes 的 primefactors，请考虑以下示例:

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