Quel est le moyen le plus efficace de trouver tous les facteurs d'un nombre en Python?
https://stackoverflow.com/questions/6800193
-
22-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelqu'un peut-il me expliquer un moyen efficace de trouver tous les facteurs d'un nombre en Python (2.7)?
Je peux créer un algorithme pour ce faire, mais je pense qu'il est mal codé et prend trop de temps pour produire un résultat pour un grand nombre.
La solution
from functools import reduce
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)))
Ceci renvoie tous les facteurs, très rapidement, d'un certain nombre n.
Pourquoi la 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 plus grand facteur, vous devez rendre l'autre plus petit facteur. Cela signifie que l'un des deux sera toujours inférieure ou égale à sqrt(x), donc il suffit de chercher jusqu'à ce moment-là pour trouver l'un des deux facteurs correspondants. Vous pouvez ensuite utiliser x / fac1 pour obtenir fac2.
Le reduce(list.__add__, ...) prend les petites listes de [fac1, fac2] et les réunir dans une longue liste.
Le [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 on divise par n le plus petit est égal à zéro (il n'a pas besoin de vérifier la plus grande aussi, il obtient juste que en divisant par n le plus petit.)
Le set(...) à l'extérieur est de se débarrasser des doublons, ce qui ne se produit que pour des carrés parfaits. Pour n = 4, cela retournera 2 deux fois, alors set se débarrasse d'un d'entre eux.
Autres conseils
La solution présentée par @agf est grande, mais on peut atteindre ~ 50% plus rapide pour le temps d'exécution arbitraire impair nombre en vérifiant la parité. Comme les facteurs d'un nombre impair sont eux-mêmes toujours étrange, il est nécessaire de vérifier ces lorsqu'ils traitent avec des nombres impairs.
Je viens de commencer à résoudre les énigmes Project Euler moi-même. Dans certains problèmes, un chèque de diviseur est appelé à l'intérieur de deux boucles de for imbriquées, et la performance de cette fonction est donc essentielle.
La combinaison de ce fait avec une solution excellente de faa, je l'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, un petit nombre (<~ 100), la surcharge supplémentaire de cette altération peut entraîner la fonction de prendre plus de temps.
J'ai couru quelques tests afin de vérifier la vitesse. Voici le code utilisé. Pour produire les différentes parcelles, j'ai modifié le 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 = distance (1,100,1)
ici Aucune différence significative, mais avec des chiffres plus importants, l'avantage est évident:
X = distance (1,100000,1000) (seuls les nombres impairs)
X = distance (2,100000,100) (seuls les nombres pairs)
X = distance (1,100000,1001) (parité alternée)
qu'AGF vraiment tout à fait refroidir. Je voulais voir si je pouvais réécrire pour éviter d'utiliser 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 essayé aussi une version qui utilise des fonctions de générateur délicat:
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)
I chronométré en calculant:
start = 10000000
end = start + 40000
for n in range(start, end):
factors(n)
je l'ai couru une fois pour laisser Python compiler, puis il a couru sous le temps (1) commande trois fois et gardé le meilleur temps.
- réduire la version: 11,58 secondes
- itertools version: 11,49 secondes
- Version délicate: 11.12 secondes
Notez que la version itertools construit un tuple et passant à flatten_iter (). Si je change le code pour construire une liste à la place, il ralentit légèrement:
- iterools (liste) Version: 11,62 secondes
Je crois que la version délicate des fonctions du générateur est le plus rapide possible en Python. Mais ce n'est pas vraiment beaucoup plus rapide que la réduire la version, environ 4% plus rapide en fonction de mes mesures.
Une approche alternative à la réponse de faa:
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
Je l'ai essayé la plupart de ces merveilleuses réponses avec timeit de comparer leur efficacité par rapport à ma fonction simple et pourtant je vois constamment mes surclassent celles qui sont énumérées ici. Je pensais que je devais partager et voir ce que vous pensez tous.
def factors(n):
results = set()
for i in xrange(1, int(math.sqrt(n)) + 1):
if n % i == 0:
results.add(i)
results.add(int(n/i))
return results
Comme il est écrit que vous devrez les mathématiques à l'importation pour tester, mais en remplaçant math.sqrt (n) avec n **. 5 devrait fonctionner tout aussi bien. Je ne prends pas la peine de perdre de temps pour vérifier la présence de doublons, car les doublons ne peuvent pas exister dans un ensemble peu importe.
Poursuite de l'amélioration de l'AFG et la solution de eryksun. La pièce de code suivant retourne une liste triée de tous les facteurs sans changer le temps d'exécution complexité asymptotique:
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 fonction list.sort () pour obtenir une liste triée qui donne nlog (n) la complexité; Il est beaucoup plus rapide list.reverse à l'utilisation () sur l2 qui prend O (n) complexité. (Voilà comment python est fait.) Après l2.reverse (), l2 peut être ajoutée à obtenir la l1 liste triée des facteurs.
Avis, contient i -s qui augmentent. l2 contient q -s qui diminuent. Cest la raison derrière l'utilisation de l'idée ci-dessus.
Voici une alternative à la solution de @ faa qui met en oeuvre le même algorithme dans un style plus pythonique:
def factors(n):
return set(
factor for i in range(1, int(n**0.5) + 1) if n % i == 0
for factor in (i, n//i)
)
Cette solution fonctionne à la fois Python 2 et Python 3 sans les importations et est beaucoup plus facile à lire. Je ne l'ai pas testé les performances de cette approche, mais asymptotiquement il devrait être le même, et si la performance est une préoccupation sérieuse, ni solution est optimale.
Pour n jusqu'à 10 ** 16 (peut-être même un peu plus), voici une solution Python 3.6 rapide pur,
from itertools import compress
def primes(n):
""" Returns a list of primes < n for n > 2 """
sieve = bytearray([True]) * (n//2)
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
return [2,*compress(range(3,n,2), sieve[1:])]
def factorization(n):
""" Returns a list of the prime factorization of n """
pf = []
for p in primeslist:
if p*p > n : break
count = 0
while not n % p:
n //= p
count += 1
if count > 0: pf.append((p, count))
if n > 1: pf.append((n, 1))
return pf
def divisors(n):
""" Returns an unsorted list of the divisors of n """
divs = [1]
for p, e in factorization(n):
divs += [x*p**k for k in range(1,e+1) for x in divs]
return divs
n = 600851475143
primeslist = primes(int(n**0.5)+1)
print(divisors(n))
Il y a un algorithme de force de l'industrie dans sympy appelé factorint :
>>> from sympy import factorint
>>> factorint(2**70 + 3**80)
{5: 2,
41: 1,
101: 1,
181: 1,
821: 1,
1597: 1,
5393: 1,
27188665321L: 1,
41030818561L: 1}
Cela a pris moins d'une minute. Il passe entre un cocktail de méthodes. Consultez la documentation liée ci-dessus.
Compte tenu de tous les facteurs premiers, tous les autres facteurs peut être construit facilement.
Notez que même si la réponse acceptée a été autorisé à courir assez longtemps (par exemple une éternité) au facteur le numéro ci-dessus, pour certains un grand nombre, il échouera, comme l'exemple suivant. Cela est dû à la int(n**0.5) bâclée. Par exemple, lorsque n = 10000000000000079**2, nous avons
>>> int(n**0.5)
10000000000000078L
Depuis 10000000000000079 est un premier , l'algorithme de la réponse acceptée ne trouvera jamais cette facteur. Notez que ce n'est pas seulement un hors par un; pour un plus grand nombre, il sera hors de plus. Pour cette raison, il est préférable d'éviter les nombres à virgule flottante dans les algorithmes de ce genre.
Voici une autre alternative sans réduire qui fonctionne bien avec un grand nombre. Il utilise sum pour aplatir la liste.
def factors(n):
return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
Assurez-vous de saisir le plus grand nombre que sqrt(number_to_factor) pour un nombre inhabituel comme 99 qui a 3 * 3 * 11 et floor sqrt(99)+1 == 10.
import math
def factor(x):
if x == 0 or x == 1:
return None
res = []
for i in range(2,int(math.floor(math.sqrt(x)+1))):
while x % i == 0:
x /= i
res.append(i)
if x != 1: # Unusual numbers
res.append(x)
return res
Voici un exemple si vous souhaitez utiliser le nombre de nombres premiers pour aller beaucoup plus vite. Ces listes sont faciles à trouver sur Internet. J'ai ajouté des commentaires dans le code.
# http://primes.utm.edu/lists/small/10000.txt
# First 10000 primes
_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
# Mising a lot of primes for the purpose of the example
)
from bisect import bisect_left as _bisect_left
from math import sqrt as _sqrt
def get_factors(n):
assert isinstance(n, int), "n must be an integer."
assert n > 0, "n must be greather than zero."
limit = pow(_PRIMES[-1], 2)
assert n <= limit, "n is greather then the limit of {0}".format(limit)
result = set((1, n))
root = int(_sqrt(n))
primes = [t for t in get_primes_smaller_than(root + 1) if not n % t]
result.update(primes) # Add all the primes factors less or equal to root square
for t in primes:
result.update(get_factors(n/t)) # Add all the factors associted for the primes by using the same process
return sorted(result)
def get_primes_smaller_than(n):
return _PRIMES[:_bisect_left(_PRIMES, n)]
un algorithme potentiellement plus efficace que ceux présentés ici déjà (surtout s'il y a des petites premiers factons dans n). l'astuce est ici ajuster la limite jusqu'à laquelle la division d'essai est nécessaire à chaque fois que les premiers facteurs se trouvent:
def factors(n):
'''
return prime factors and multiplicity of n
n = p0^e0 * p1^e1 * ... * pk^ek encoded as
res = [(p0, e0), (p1, e1), ..., (pk, ek)]
'''
res = []
# get rid of all the factors of 2 using bit shifts
mult = 0
while not n & 1:
mult += 1
n >>= 1
if mult != 0:
res.append((2, mult))
limit = round(sqrt(n))
test_prime = 3
while test_prime <= limit:
mult = 0
while n % test_prime == 0:
mult += 1
n //= test_prime
if mult != 0:
res.append((test_prime, mult))
if n == 1: # only useful if ek >= 3 (ek: multiplicity
break # of the last prime)
limit = round(sqrt(n)) # adjust the limit
test_prime += 2 # will often not be prime...
if n != 1:
res.append((n, 1))
return res
est de la division cours d'essai encore et rien de plus de fantaisie. et donc encore très limitée dans son efficacité (en particulier pour les grands nombres sans petits diviseurs).
est python3; la // division devrait être la seule chose que vous devez adapter pour python 2 (add from __future__ import division).
votre facteur maximum ne dépasse pas votre numéro, donc, disons que
def factors(n):
factors = []
for i in range(1, n//2+1):
if n % i == 0:
factors.append (i)
factors.append(n)
return factors
voilá!
La façon la plus simple de trouver des facteurs d'un nombre:
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
Utilisation set(...) rend le code un peu plus lent, et n'est vraiment nécessaire lorsque vous vérifiez la racine carrée. Voici ma version:
def factors(num):
if (num == 1 or num == 0):
return []
f = [1]
sq = int(math.sqrt(num))
for i in range(2, sq):
if num % i == 0:
f.append(i)
f.append(num/i)
if sq > 1 and num % sq == 0:
f.append(sq)
if sq*sq != num:
f.append(num/sq)
return f
La condition de if sq*sq != num: est nécessaire pour les nombres comme 12, où la racine carrée est pas un nombre entier, mais le plancher de la racine carrée est un facteur.
Notez que cette version ne retourne pas le nombre lui-même, mais qui est une solution facile si vous le voulez. La sortie ne sont pas triées aussi.
je l'ai chronométré courir 10000 fois sur tous les numéros 1-200 et 100 fois sur tous les numéros 1-5000. Il surclasse toutes les autres versions I testés, y compris dansalmo de Jason Schorn, de son oxrock, agf de, de steveha et les solutions de eryksun, bien que ce oxrock est de loin le plus proche.
Utilisez quelque chose d'aussi simple que la compréhension de la liste suivante, en notant que nous ne avons pas besoin de tester 1 et le nombre que nous essayons de trouver:
def factors(n):
return [x for x in range(2, n//2+1) if n%x == 0]
En ce qui concerne l'utilisation de la racine carrée, disons que nous voulons trouver des facteurs de 10. La partie entière du sqrt(10) = 4 donc range(1, int(sqrt(10))) = [1, 2, 3, 4] et tester jusqu'à 4 manque clairement 5.
À moins que je manque quelque chose que je suggère, si vous devez le faire de cette façon, en utilisant int(ceil(sqrt(x))). Bien sûr, cela produit un grand nombre d'appels inutiles aux fonctions.
Je pense que pour la lisibilité et la vitesse @ solution de oxrock est le meilleur, alors voici le code réécrite pour python 3 +:
def num_factors(n):
results = set()
for i in range(1, int(n**0.5) + 1):
if n % i == 0: results.update([i,int(n/i)])
return results
J'ai été très surpris quand j'ai vu cette question que personne ne numpy utilisé même lorsque numpy est façon plus rapide que les boucles de python. En mettant en œuvre la solution de @ avec faa numpy et il est apparu à la moyenne 8x plus rapide . Je belive que si vous mis en œuvre certaines des autres solutions numpy vous pourriez obtenir des temps incroyables.
Voici ma fonction:
import numpy as np
def b(n):
r = np.arange(1, int(n ** 0.5) + 1)
x = r[np.mod(n, r) == 0]
return set(np.concatenate((x, n / x), axis=None))
Notez que les nombres de l'axe x ne sont pas l'entrée des fonctions. L'entrée des fonctions est de 2 à nombre sur l'axe des x de moins 1. Alors, où dix est l'entrée serait 2 ** 10-1 = 1023
import 'dart:math';
generateFactorsOfN(N){
//determine lowest bound divisor range
final lowerBoundCheck = sqrt(N).toInt();
var factors = Set<int>(); //stores factors
/**
* Lets take 16:
* 4 = sqrt(16)
* start from 1 ... 4 inclusive
* check mod 16 % 1 == 0? set[1, (16 / 1)]
* check mod 16 % 2 == 0? set[1, (16 / 1) , 2 , (16 / 2)]
* check mod 16 % 3 == 0? set[1, (16 / 1) , 2 , (16 / 2)] -> unchanged
* check mod 16 % 4 == 0? set[1, (16 / 1) , 2 , (16 / 2), 4, (16 / 4)]
*
* ******************* set is used to remove duplicate
* ******************* case 4 and (16 / 4) both equal to 4
* return factor set<int>.. this isn't ordered
*/
for(var divisor = 1; divisor <= lowerBoundCheck; divisor++){
if(N % divisor == 0){
factors.add(divisor);
factors.add(N ~/ divisor); // ~/ integer division
}
}
return factors;
}
import math
'''
I applied finding prime factorization to solve this. (Trial Division)
It's not complicated
'''
def generate_factors(n):
lower_bound_check = int(math.sqrt(n)) # determine lowest bound divisor range [16 = 4]
factors = set() # store factors
for divisors in range(1, lower_bound_check + 1): # loop [1 .. 4]
if n % divisors == 0:
factors.add(divisors) # lower bound divisor is found 16 [ 1, 2, 4]
factors.add(n // divisors) # get upper divisor from lower [ 16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4]
return factors # [1, 2, 4, 8 16]
print(generate_factors(12)) # {1, 2, 3, 4, 6, 12} -> pycharm output
Pierre Vriens hopefully this makes more sense. this is an O(nlogn) solution.
Je pense que c'est la façon de faire plus simple que:
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1
