Quel est le moyen le plus efficace de trouver tous les facteurs d’un nombre en Python?

Question

Est-ce que quelqu'un peut m'expliquer un moyen efficace de trouver tous les facteurs d'un nombre dans Python (2.7)?

Je peux créer des algorithmes pour faire ce travail, mais je pense qu'il est mal codé et prend trop de temps pour exécuter un résultat pour un grand nombre.

Answer 1

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

Ce sera le retour de tous les facteurs, très rapidement, d'un certain nombre n.

Pourquoi racine carrée comme la limite supérieure?

sqrt(x) * sqrt(x) = x. Donc, si les deux facteurs sont les mêmes, ils sont à la fois la racine carrée. Si vous faites un facteur de plus, vous devez vous rendre de l'autre facteur plus petit. Cela signifie que l'un des deux sera toujours inférieure ou égale à sqrt(x), de sorte que vous n'avez à la recherche jusqu'à ce point pour trouver l'un des deux correspondants facteurs. Vous pouvez ensuite utiliser x / fac1 pour obtenir de l' fac2

l' reduce(list.__add__, ...) est de prendre le peu de listes d' [fac1, fac2] et se réunissant dans une longue liste.

L' [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 retourne une paire de facteurs si le reste quand vous divisez n par la plus petite est de zéro (il n'a pas besoin de vérifier le plus grand, trop, c'est juste qu'en divisant n par le plus petit.)

L' set(...) sur l'extérieur est de se débarrasser des doublons. Je pense que cela ne se produit que pour des carrés parfaits. Pour n = 4, ce sera le retour de 2 deux fois, alors set se débarrasser de l'un d'eux.

Edit: sqrt est effectivement plus rapide que l' **0.5, mais je vais le laisser comme il est beau comme un fragment de code.

Answer 2

La solution présentée par @agf est grande, mais on peut parvenir à ~50% plus rapide temps d'exécution pour un arbitraire impair nombre par la vérification de la parité. Comme les facteurs d'un nombre impair est toujours impair eux-mêmes, il n'est pas nécessaire de vérifier ces lorsque vous traitez avec des nombres impairs.

Je viens de commencer la résolution d'Euler puzzles de moi-même. Dans certains problèmes, un diviseur de contrôle est appelée à l'intérieur de deux boucles for imbriquées, et la performance de cette fonction est donc essentiel.

La combinaison de cet effet avec agf est une excellente solution, j'ai fini avec cette fonction.

from math import sqrt    
def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

Cependant, sur de petits nombres (~ < 100), les frais généraux supplémentaires à partir de cette altération peut provoquer la fonction de prendre plus de temps.

J'ai couru quelques tests afin de vérifier la vitesse. Ci-dessous est le code utilisé. Pour produire les différentes parcelles, j'ai changé l' X = range(1,100,1) en conséquence.

import timeit
from math import sqrt
from matplotlib.pyplot import plot, legend, show

def factors_1(n):
    step = 2 if n%2 else 1
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

def factors_2(n):
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

X = range(1,100000,1000)
Y = []
for i in X:
    f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
    f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
    Y.append(f_1/f_2)
plot(X,Y, label='Running time with/without parity check')
legend()
show()

X = range(1,100,1)

Aucune différence significative ici, mais avec de plus grands nombres, l'avantage est évident:

X = range(1,100000,1000) (seuls les numéros impairs)

X = range(2,100000,100) (uniquement des chiffres)

X = range(1,100000,1001) (en alternance de la parité)

Answer 3

agf réponse est vraiment très cool. Je voulais voir si je pouvais réécrire à éviter d'utiliser des reduce(). C'est ce que je suis venu avec:

import itertools
flatten_iter = itertools.chain.from_iterable
def factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

J'ai aussi essayé une version qui utilise délicat générateur de fonctions:

def factors(n):
    return set(x for tup in ([i, n//i] 
                for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)

Je l'ai chronométré par le calcul:

start = 10000000
end = start + 40000
for n in range(start, end):
    factors(n)

J'ai couru une fois à Python compiler, puis il a couru sous la commande time(1) à trois reprises et a gardé le meilleur temps.

• réduire version: 11.58 secondes
• itertools version: 11.49 secondes
• difficile de version: 11.12 secondes

Notez que le itertools version est la construction d'un n-uplet et en passant à flatten_iter(). Si je change le code pour générer une liste au lieu de cela, il ralentit légèrement:

• iterools (liste) version: 11.62 secondes

Je crois que le plus compliqué générateur de fonctions est la version la plus rapide possible en Python. Mais ce n'est pas vraiment beaucoup plus rapide que de le réduire version, environ 4% plus rapide basé sur mes mesures.

Answer 4

Une approche alternative à la réponse de agf:

 def factors(n):    
    result = set()
    for i in range(1, int(n ** 0.5) + 1):
        div, mod = divmod(n, i)
        if mod == 0:
            result |= {i, div}
    return result
 

Answer 5

La poursuite de l'amélioration de l'afg et eryksun de la solution. Le morceau de code suivant renvoie une liste triée de tous les facteurs sans changer de temps d'exécution asymptotique de la complexité:

    def factors(n):    
        l1, l2 = [], []
        for i in range(1, int(n ** 0.5) + 1):
            q,r = n//i, n%i     # Alter: divmod() fn can be used.
            if r == 0:
                l1.append(i) 
                l2.append(q)    # q's obtained are decreasing.
        if l1[-1] == l2[-1]:    # To avoid duplication of the possible factor sqrt(n)
            l1.pop()
        l2.reverse()
        return l1 + l2

Idée: au Lieu d'utiliser la liste.fonction sort() pour obtenir une liste triée qui donne nlog(n) la complexité; Il est beaucoup plus rapide à utiliser la liste.reverse() sur l2 qui prend O(n) la complexité. (C'est comme python). Après la l2.reverse(), l2 peut être ajoutée à la l1 pour obtenir la liste triée des facteurs.

Avis, l1 contient i-s qui sont en augmentation. l2 contient q-s qui sont en baisse. C'est la raison derrière l'utilisation de l'idée ci-dessus.