¿Cuál es la mejor manera de obtener todos los divisores de un número?

Aquí está la manera muy tonta:

def divisorGenerator(n): for i in xrange(1,n/2+1): if n%i == 0: yield i yield n 

El resultado que me gustaría obtener es similar a este, pero me gustaría un algoritmo más inteligente (este es demasiado lento y tonto 🙂

Puedo encontrar los factores primos y su multiplicidad lo suficientemente rápido. Tengo un generador que genera factor de esta manera:

(factor1, multiplicidad1)
(factor2, multiplicidad2)
(factor3, multiplicidad3)
y así…

es decir, la salida de

 for i in factorGenerator(100): print i 

es:

 (2, 2) (5, 2) 

No sé cuánto es útil para lo que quiero hacer (lo codifiqué para otros problemas), de todos modos me gustaría una forma más inteligente de hacer

 for i in divisorGen(100): print i 

salida esto:

 1 2 4 5 10 20 25 50 100 

ACTUALIZACIÓN: Muchas gracias a Greg Hewgill y su “manera inteligente” 🙂 Al calcular todos los divisores de 100000000, tomé 0.01s en su camino contra los 39s que la forma tonta tomó en mi máquina, muy bueno: D

ACTUALIZACIÓN 2: deja de decir que esto es un duplicado de esta publicación. Calcular el número de divisor de un número dado no necesita calcular todos los divisores. Es un problema diferente, si crees que no es así, busca la “función del Divisor” en wikipedia. Lea las preguntas y la respuesta antes de publicar, si no entiende cuál es el tema, no agregue nada útil y respuestas ya dadas.

Dada tu función factorGenerator, aquí hay un divisorGen que debería funcionar:

 def divisorGen(n): factors = list(factorGenerator(n)) nfactors = len(factors) f = [0] * nfactors while True: yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1) i = 0 while True: f[i] += 1 if f[i] <= factors[i][1]: break f[i] = 0 i += 1 if i >= nfactors: return 

La eficiencia general de este algoritmo dependerá completamente de la eficiencia del factorGenerator.

Para ampliar lo que Shimi ha dicho, solo debes ejecutar tu bucle desde 1 hasta la raíz cuadrada de n. Luego, para encontrar el par, haga n / i , y esto cubrirá todo el espacio del problema.

Como también se señaló, este es un problema de NP o “difícil”. La búsqueda exhaustiva, la forma en que lo está haciendo, es tan buena como la respuesta garantizada. Este hecho es utilizado por los algoritmos de cifrado y similares para ayudar a asegurarlos. Si alguien resolviera este problema, la mayoría de nuestras comunicaciones “seguras” actuales, si no todas, se volverían inseguras.

Código Python:

 import math def divisorGenerator(n): large_divisors = [] for i in xrange(1, int(math.sqrt(n) + 1)): if n % i == 0: yield i if i*i != n: large_divisors.append(n / i) for divisor in reversed(large_divisors): yield divisor print list(divisorGenerator(100)) 

Lo que debería dar salida a una lista como:

 [1, 2, 4, 5, 10, 20, 25, 50, 100]

Creo que puedes parar en math.sqrt(n) lugar de n / 2.

Te daré un ejemplo para que puedas entenderlo fácilmente. Ahora el sqrt(28) es 5.29 así que ceil(5.29) será 6. Entonces, si me detengo en 6, puedo obtener todos los divisores. ¿Cómo?

Primero vea el código y luego vea la imagen:

 import math def divisors(n): divs = [1] for i in xrange(2,int(math.sqrt(n))+1): if n%i == 0: divs.extend([i,n/i]) divs.extend([n]) return list(set(divs)) 

Ahora, vea la siguiente imagen:

Digamos que ya he agregado 1 a mi lista de divisores y comienzo con i=2 así que

Divisores de un 28

Así que al final de todas las iteraciones, ya que he agregado el cociente y el divisor a mi lista, todos los divisores de 28 están poblados.

Espero que esto ayude. Si tiene alguna duda, no dude en volver a responder y estaré encantado de ayudarle :).

Fuente: Cómo determinar los divisores de un número.
Radio del círculo – Código e imagen

Aunque ya hay muchas soluciones para esto, realmente tengo que publicar esto 🙂

Este es:

  • legible
  • corto
  • autónomo, listo para copiar y pegar
  • rápido (en casos con muchos factores primos y divisores, 10 veces más rápido que la solución aceptada)
  • Python3, python2 y pypy compatibles

Código:

 def divisors(n): # get factors and their counts factors = {} nn = n i = 2 while i*i <= nn: while nn % i == 0: factors[i] = factors.get(i, 0) + 1 nn //= i i += 1 if nn > 1: factors[nn] = factors.get(nn, 0) + 1 primes = list(factors.keys()) # generates factors from primes[k:] subset def generate(k): if k == len(primes): yield 1 else: rest = generate(k+1) prime = primes[k] for factor in rest: prime_to_i = 1 # prime_to_i iterates prime**i values, i being all possible exponents for _ in range(factors[prime] + 1): yield factor * prime_to_i prime_to_i *= prime # in python3, `yield from generate(0)` would also work for factor in generate(0): yield factor 

Me gusta la solución de Greg, pero desearía que fuera más parecida a una python. Siento que sería más rápido y más legible; Así que después de un tiempo de encoding salí con esto.

Las dos primeras funciones son necesarias para hacer el producto cartesiano de listas. Y se puede reutilizar cuando surja este problema. Por cierto, tuve que progtwigrlo yo mismo, si alguien sabe de una solución estándar para este problema, no dude en contactarme.

“Factorgenerator” ahora devuelve un diccionario. Y luego el diccionario se alimenta en “divisores”, que lo utilizan para generar primero una lista de listas, donde cada lista es la lista de los factores de la forma p ^ n con p prime. Luego hacemos el producto cartesiano de esas listas y finalmente usamos la solución de Greg para generar el divisor. Los ordenamos, y los devolvemos.

Lo probé y parece ser un poco más rápido que la versión anterior. Lo probé como parte de un progtwig más grande, así que no puedo decir cuánto es más rápido.

Pietro Speroni (pietrosperoni dot it)

 from math import sqrt ############################################################## ### cartesian product of lists ################################## ############################################################## def appendEs2Sequences(sequences,es): result=[] if not sequences: for e in es: result.append([e]) else: for e in es: result+=[seq+[e] for seq in sequences] return result def cartesianproduct(lists): """ given a list of lists, returns all the possible combinations taking one element from each list The list does not have to be of equal length """ return reduce(appendEs2Sequences,lists,[]) ############################################################## ### prime factors of a natural ################################## ############################################################## def primefactors(n): '''lists prime factors, from greatest to smallest''' i = 2 while i<=sqrt(n): if n%i==0: l = primefactors(n/i) l.append(i) return l i+=1 return [n] # n is prime ############################################################## ### factorization of a natural ################################## ############################################################## def factorGenerator(n): p = primefactors(n) factors={} for p1 in p: try: factors[p1]+=1 except KeyError: factors[p1]=1 return factors def divisors(n): factors = factorGenerator(n) divisors=[] listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()] listfactors=cartesianproduct(listexponents) for f in listfactors: divisors.append(reduce(lambda x, y: x*y, f, 1)) divisors.sort() return divisors print divisors(60668796879) 

PD: es la primera vez que publico en stackoverflow. Estoy esperando por cualquier comentario.

Adaptado de CodeReview , aquí hay una variante que funciona con num=1 !

 from itertools import product import operator def prod(ls): return reduce(operator.mul, ls, 1) def powered(factors, powers): return prod(f**p for (f,p) in zip(factors, powers)) def divisors(num) : pf = dict(prime_factors(num)) primes = pf.keys() #For each prime, possible exponents exponents = [range(i+1) for i in pf.values()] return (powered(primes,es) for es in product(*exponents)) 

Antigua pregunta, pero aquí está mi opinión:

 def divs(n, m): if m == 1: return [1] if n % m == 0: return [m] + divs(n, m - 1) return divs(n, m - 1) 

Puedes proxy con:

 def divisorGenerator(n): for x in reversed(divs(n, n)): yield x 

NOTA: Para los idiomas que admiten, esto podría ser recursivo.

Esta es una forma inteligente y rápida de hacerlo para números de hasta alrededor de 10 ** 16 en Python 3.6 puro,

 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((ni*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)) 

Solo voy a agregar una versión ligeramente revisada de Anivarth (ya que creo que es la más python) para futuras referencias.

 from math import sqrt def divisors(n): divs = {1,n} for i in range(2,int(sqrt(n))+1): if n%i == 0: divs.update((i,n//i)) return divs 

Suponiendo que la función de factors devuelve los factores de n (por ejemplo, los factors(60) devuelve la lista [2, 2, 3, 5]), aquí hay una función para calcular los divisores de n :

 function divisors(n) divs := [1] for fact in factors(n) temp := [] for div in divs if fact * div not in divs append fact * div to temp divs := divs + temp return divs 

Aquí está mi solución. Parece ser tonto, pero funciona bien … y estaba tratando de encontrar todos los divisores adecuados, por lo que el ciclo comenzó desde i = 2.

 import math as m def findfac(n): faclist = [1] for i in range(2, int(m.sqrt(n) + 2)): if n%i == 0: if i not in faclist: faclist.append(i) if n/i not in faclist: faclist.append(n/i) return facts 

¡Si solo te importa utilizar listas de comprensión y nada más te importa!

 from itertools import combinations from functools import reduce def get_devisors(n): f = [f for f,e in list(factorGenerator(n)) for i in range(e)] fc = [x for l in range(len(f)+1) for x in combinations(f, l)] devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)] return sorted(devisors) 
 return [x for x in range(n+1) if n/x==int(n/x)] 

Para mí esto funciona bien y también está limpio (Python 3)

 def divisors(number): n = 1 while(n 

No es muy rápido pero devuelve los divisores línea por línea como usted desea, también puede hacer list.append (n) y list.append (número) si realmente desea