我有一个数字的素因子的Python列表.我如何(pythonically)找到所有因素？

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列表重复,itertools.combinations正好满足您的需求 - 您只需要len(primefactors) - 1包含长度为2的项目组合(仅一个的组合是主要因素,即所有项目的组合)它们将是原始数字 - 如果你也想要那些,只需使用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

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没有在这里实现,但你明白了(两者写起来都很简单)

恕我直言,作为数学问题,欧拉问题可以使用功能而不是命令式风格很好地解决(虽然我承认某些解决方案可能不会像所希望的那样以pythonic形式出现).