python - saber - ¿Cuál es la mejor manera de obtener todos los divisores de un número?
programa para sacar los multiplos de un numero python (13)
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 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, el resultado 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" :) Cálculo de todos los divisores de 100000000 tomó 0.01s con su camino contra los 39s que el modo tonto tomó en mi máquina, muy genial: D
ACTUALIZACIÓN 2: Deja de decir que este es un duplicado de this publicación. El cálculo del número de divisores 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 Divisor" en wikipedia. Lee las preguntas y la respuesta antes de publicar, si no entiendes cuál es el tema solo no agregues respuestas no útiles y ya dadas.
¡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))
¡Si solo te importa usar 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)
Aquí está mi solución. Parece ser tonto pero funciona bien ... y yo estaba tratando de encontrar todos los divisores adecuados para que el ciclo comenzara 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
Aquí hay una manera inteligente y rápida de hacerlo con números de hasta 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((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))
Aunque ya hay muchas soluciones para esto, realmente tengo que publicar esto :)
Este es:
- legible
- corto
- auto contenido, copiar y pegar listo
- rápido (en casos con muchos factores primos y divisores,> 10 veces más rápido que la solución de Greg)
- python3, python2 y pypy obedientes
Código:
def divisors(n):
# get factors and their counts
factors = {}
nn = n
i = 2
while i*i <= nn:
while nn % i == 0:
if not i in factors:
factors[i] = 0
factors[i] += 1
nn //= i
i += 1
if nn > 1:
factors[nn] = 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
Creo que puede detenerse en math.sqrt(n) lugar de n / 2.
Le daré un ejemplo para que pueda entenderlo fácilmente. Ahora el sqrt(28) es 5.29 por lo que ceil(5.29) será 6. Entonces, si me detengo en 6, entonces podré 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, mira la imagen a continuación:
Digamos que ya he agregado 1 a mi lista de divisores y comienzo con i=2 por lo
Entonces, 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 ocupados.
Espero que esto ayude. Si tienes alguna duda, no dudes en enviar un mensaje de vuelta y estaré encantado de ayudarte :).
Fuente: cómo determinar los divisores de un número
Radio de círculo : código e imagen
Dada su 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á por completo de la eficiencia del Factor Generador.
Me gusta la solución de Greg, pero me gustaría que fuera más parecido a Python. Siento que sería más rápido y más legible; así que después de un tiempo de codificación, salí con esto.
Las dos primeras funciones son necesarias para hacer el producto cartesiano de listas. Y puede reutilizarse siempre que surja este problema. Por cierto, tuve que programarlo yo mismo, si alguien sabe de una solución estándar para este problema, no dude en ponerse en contacto conmigo.
"Factorgenerator" ahora devuelve un diccionario. Y luego el diccionario se introduce en "divisores", que lo usa 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 clasificamos 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 programa más grande, así que no puedo decir cuánto es más rápido.
Pietro Speroni (pietrosperoni punto)
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 . Estoy esperando cualquier comentario.
Para ampliar lo que ha dicho Shimi, solo deberías ejecutar tu ciclo de 1 a la raíz cuadrada de n. Luego, para encontrar el par, haz n / i , y esto cubrirá todo el espacio del problema.
Como también se señaló, este es un NP, o problema ''difícil''. La búsqueda exhaustiva, la forma en que lo está haciendo, es casi tan buena como lo es para obtener respuestas garantizadas. Este hecho es utilizado por algoritmos de encriptación y similares para ayudar a protegerlos. Si alguien resolviera este problema, la mayoría, si no toda, nuestra comunicación actual "segura" quedaría insegura.
Código de 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))
Que debería generar una lista como:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Para mí esto funciona bien y también está limpio (Python 3)
def divisors(number):
n = 1
while(n<number):
if(number%n==0):
print(n)
else:
pass
n += 1
print(number)
No es muy rápido, pero devuelve los divisores línea por línea como quisiera, también puede hacer list.append (n) y list.append (number) si realmente desea
Suponiendo que la función de factors devuelve los factores de n (por ejemplo, los factors(60) devuelven 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
Una vieja pregunta, pero esta es 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)
Puede 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 de cola.
return [x for x in range(n+1) if n/x==int(n/x)]