J'ai une liste Python des facteurs premiers d'un nombre. Comment puis-je (pythonically) trouve tous les facteurs?

Question

Je travaille sur un problème d'Euler projet qui nécessite factorisation d'un entier. Je peux trouver une liste de tous les nombres premiers qui sont le facteur d'un nombre donné. Le théorème fondamental de l'arithmétique implique que je peux utiliser cette liste pour Derive tous les facteurs du nombre.

Mon plan actuel est de prendre chaque numéro dans la liste des nombres premiers de base et augmenter sa puissance jusqu'à ce qu'il ne soit plus un facteur entier pour trouver les exposants maximum pour chaque prime. Ensuite, je vais multiplier toutes les combinaisons possibles de paires prime-exposant.

Ainsi, par exemple, pour 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.

Ensuite, faire toutes les combinaisons de ceux-ci jusqu'à l'exposant maximum pour obtenir les facteurs:

    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

Ainsi, la liste de facteurs = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

Voici le code que j'ai jusqu'à présent. Deux problèmes: D'abord, je ne pense pas que ce soit très Pythonic du tout. Je voudrais corriger cela. Deuxièmement, je vraiment n'ont pas une façon de faire Pythonic la deuxième étape combinatoires. De honte, je vous ai épargné de l'ensemble ridicule de boucles.

n est le nombre que nous voulons facteur. listOfAllPrimes une liste précalculée des nombres premiers jusqu'à 10 millions.

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

Au lieu d'une liste des exposants, il suffit de considérer répéter chaque facteur premier par le nombre de fois où il un facteur. Après cela, le travail sur la liste primefactors résultant avec-répétitions, itertools.combinations fait exactement ce que vous avez besoin - vous aurez juste besoin des combinaisons de longueur 2 à des éléments de len(primefactors) - 1 inclus (les combinaisons d'un seul sont les facteurs principaux, celui de tous sera le nombre initial - si vous voulez les aussi, il suffit d'utiliser range(1, len(primefactors) + 1) au lieu de range(2, len(primefactors)) que ma suggestion principale utiliserait).

Il y aura des répétitions dans les résultats (par exemple, 6 apparaissent deux fois comme facteur de 12, puisque celui-ci de primefactors sera [2, 2, 3]) et ils peuvent bien sûr être éliminés de la manière habituelle (c.-à-sorted(set(results)) par exemple).

Pour calculer primefactors donné de listOfAllPrimes, pensez par exemple:

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

Pourquoi voulez-vous commencer votre solution de l'ensemble des facteurs premiers? lorsque vous factoriser un numéro, vous pouvez aussi facilement obtenir tous ses facteurs premiers (répétés) et d'eux les exposants pour chaque facteur. Avec cela à l'esprit, vous pouvez écrire ceci:

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 et product ne sont pas mises en œuvre ici, mais vous avez l'idée (les deux sont assez simples à écrire)

à mon humble avis, être des problèmes mathématiques, les problèmes d'Euler peut être bien résolu en utilisant à la place fonctionnelle du style impératif (si je reconnais que certaines solutions ne peuvent venir que pythonique comme vous le souhaitez).

Answer 3

Vous pouvez utiliser itertools.combinations() pour obtenir toutes les combinaisons possibles de facteurs une fois que vous avez obtenu votre liste de nombres premiers-répétés, comme [2, 2, 3, 3, 5] pour 180. Ensuite, en multipliant simplement les composants de chaque combinaison vous obtiendrez un facteur.

Answer 4

Avec un peu plus fraîche caractéristiques 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

Answer 5

Voici une solution simple et efficace au problème initial:

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

La liste de sortie est non triés. Vous pouvez le rendre plus « pythonique » si vous voulez, quoi que cela signifie.

Answer 6

Une solution tout en un; dire pas besoin d'une liste existante des principaux facteurs.

#!/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))

Remarque [1] : En tant que générateur de nombres premiers, vous pouvez choisir un de Comment mettre en œuvre un système efficace générateur infini de nombres premiers en Python? ou utilisez votre propre (par exemple votre listOfAllPrimes).

Ceci produit une liste complète des facteurs, à savoir notamment 1 et l'argument number lui-même. Si vous voulez omettre ceux-ci, vous pouvez utiliser 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])