У меня есть список простых чисел числа Python. Как мне (на питонском языке) найти все факторы?

Ответ 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

Ответ 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 здесь не реализованы, но вы получаете идею (оба довольно просты для записи)

IMHO, будучи математическими проблемами, проблемы Эйлера могут быть хорошо решены с использованием функционального, а не императивного стиля (хотя я признаю, что некоторые решения могут не появляться как пифонические по желанию).

Ответ 3

Вы можете использовать itertools.combinations(), чтобы получить все возможные комбинации факторов, как только вы получите список повторяющихся простых чисел, например [2, 2, 3, 3, 5] для 180. Тогда простое умножение компонентов из каждой комбинации даст вам фактор.

Ответ 4

С несколькими более крутыми функциями Python:

def factors( num ):
    for p in primes:
        if num==1: break # stop when num is 1
        while True: # these factors may be repeated 
            new, rest = divmod(num, p) # does div and mod at once
            if rest==0: # its divisible
                yield p # current prime is factor
                num = new # continue with the div'd number
            else:
                break # no factor so break from the while


print list(factors(2*2*3*3*5*7*11*11*13)) # [2, 2, 3, 3, 5, 7, 11, 11, 13] ofc

Ответ 5

Здесь простое и эффективное решение исходной задачи:

def getDivisors(n):
    divisors = []
    d = 1
    while d*d < n:
        if n % d == 0:
            divisors.append(d)
            divisors.append(n / d);
        d += 1
    if d*d == n:
        divisors.append(d)
    return divisors

Выходной список не сортируется. Вы можете сделать его более "pythonic", если хотите, что бы это ни значило.

Ответ 6

Все в одном решении; то есть нет необходимости в существующем списке простых факторов.

#!/usr/bin/python3 -O

from primegen import erat3 as generate_primes # see Note[1]
import operator as op, functools as ft, itertools as it

def all_factors(number):
    prime_powers= []

    for prime in generate_primes(): # for prime in listOfAllPrimes
        if prime > number: break

        this_prime_powers= [1]
        new_number, modulo= divmod(number, prime)

        while not modulo:
            number= new_number
            this_prime_powers.append(this_prime_powers[-1] * prime)
            new_number, modulo= divmod(number, prime)

        if len(this_prime_powers) > 1:
            prime_powers.append(this_prime_powers)

    # at this point:
    # if number was 360, prime_powers is [[1, 2, 4, 8], [1, 3, 9], [1, 5]]
    # if number was 210, prime_powers is [[1, 2], [1, 3], [1, 5], [1, 7]]

    return sorted(
        ft.reduce(op.mul, combination, 1)
        for combination in it.product(*prime_powers))

if __name__ == "__main__":
    def num_result(number):
        return number, all_factors(number)
    print(num_result(360))
    print(num_result(210))
    print(num_result(7))

Примечание [1]. Как генератор простых чисел вы можете выбрать один из Как реализовать эффективный бесконечный генератор простых чисел в Python? или используйте свой собственный (например, ваш listOfAllPrimes).

Это создает полный список факторов, т.е. включая 1 и сам аргумент number. Если вы хотите опустить их, вы можете использовать all_factors(number)[1:-1].

$ allfactors.py 
(360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360])
(210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210])
(7, [1, 7])