我有一个Python列出了一些主要因素。我如何（以Python方式）找到所有因素？

一尘不染

我有一个Python列出了一些主要因素。我如何（以Python方式）找到所有因素？

algorithm

我正在研究需要对整数进行因子分解的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]

这是我到目前为止的代码。有两个问题：首先，我认为这完全不是Python语言。我想解决这个问题。其次，我真的
没有Python方式可以完成第二步。出于耻辱，我使您摆脱了荒谬的循环。

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)

阅读 230

2020-07-28

共1个答案

一尘不染

相反，指数清单，考虑简单地重复利用的次数每一个素因子它是
一个因素。然后，处理生成primefactors的带有重复的列表，itertools.combinations即可满足您的需要-
您只需要将长度2 len(primefactors) - 1的组合包含在所包含的项目中（只有一个的组合是主要因素，所有其中一个将是原始编号-
如果您也想要这些编号，请使用range(1, len(primefactors) + 1)而不是range(2, len(primefactors))我的主要建议所使用的编号）。

结果中将存在重复（例如，6将出现的结果是的两倍12，因为后者primefactors将是[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

2020-07-28