Я работаю над проблемой 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 - это предварительно вычисленный список простых чисел до 10 миллионов.

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)