El rango es demasiado grande Python

Estoy tratando de encontrar el mayor factor primo del número x, Python me da el error de que el rango es demasiado grande. He intentado usar el rango x, pero obtengo un OverflowError: Python int demasiado grande para convertirlo en C largo

x = 600851475143 maxPrime = 0 for i in range(x): isItPrime = True if (x%i == 0): for prime in range(2,i-1): if (i%prime == 0): isItPrime = False if (isItPrime == True): if (i > maxPrime): maxPrime = i; print maxPrime 

En las versiones antiguas (2.x) de Python, xrange solo puede manejar Python 2.x int s, que están limitadas por el tamaño entero largo nativo de su plataforma. Además, el range asigna una lista con todos los números de antemano en Python 2.x, y por lo tanto no es adecuado para grandes argumentos.

Puede cambiar a 3.x (recomendado), o una plataforma donde long int (en C) tenga una longitud de 64 bits, o usar el siguiente drop-in:

 import itertools range = lambda stop: iter(itertools.count().next, stop) 

Equivalentemente, en una forma simple:

 def range(stop): i = 0 while i < stop: yield i i += 1 

Esto es lo que yo haría:

 def prime_factors(x): factors = [] while x % 2 == 0: factors.append(2) x /= 2 i = 3 while i * i <= x: while x % i == 0: x /= i factors.append(i) i += 2 if x > 1: factors.append(x) return factors >>> prime_factors(600851475143) [71, 839, 1471, 6857] 

Es bastante rápido y creo que es correcto. Es bastante simple aprovechar al máximo los factores encontrados.


2017-11-08

Volviendo a esto 5 años después, usaría el yield y el yield from conteo más rápido en el rango principal:

 def prime_factors(x): def diver(x, i): j = 0 while x % i == 0: x //= i j += 1 return x, [i] * j for i in [2, 3]: x, vals = diver(x, i) yield from vals i = 5 d = {5: 2, 1: 4} while i * i <= x: x, vals = diver(x, i) yield from vals i += d[i % 6] if x > 1: yield x list(prime_factors(600851475143)) 

El dict {5: 2, 1: 4} usa el hecho de que no tienes que mirar todos los números impares. Por encima de 3, todos los números x % 6 == 3 son múltiplos de 3, por lo que necesita mirar solo x % 6 == 1 x % 6 == 5 , y puede saltar entre ellos sumndo alternativamente 2 y 4, a partir del 5.

La respuesta aceptada sugiere un reemplazo directo para xrange, pero solo cubre un caso. Aquí hay un reemplazo más general y directo.

 def custom_range(start=0,stop=None,step=1): '''xrange in python 2.7 fails on numbers larger than C longs. we write a custom version''' if stop is None: #handle single argument case. ugly... stop = start start = 0 i = start while i < stop: yield i i += step xrange=custom_range 

Definitivamente me quedaría con xrange ya que crear una lista entre 0 y lo que parece ser un número que rivaliza con el infinito sería una carga para la memoria. xrange generará solo los números cuando se le pida. Para el problema del número demasiado grande, es posible que desee probar un “largo”. Esto se puede lograr escribiendo una L al final del número. Hice mi propia versión para probarlo. Me puse a dormir un poco para no destruir mi computadora en prácticamente un bucle de while(1) . También estaba impaciente por ver que el progtwig llegara a su fin completo, así que puse en las declaraciones impresas

 from time import sleep x = 600851475143L maxPrime = 0 for i in xrange(1,x): isItPrime = True if (x%i) == 0: for prime in xrange(2,i-1): if (i%prime) == 0: isItPrime = False break if isItPrime: maxPrime = i print "Found a prime: "+str(i) sleep(0.0000001) print maxPrime 

¡Espero que esto ayude!

EDITAR: También hice algunas ediciones más para producir esta versión. Es bastante eficiente y verifiqué algunos números que este progtwig proporciona (parece que se han verificado hasta ahora):

 from time import sleep x = 600851475143L primes = [] for i in xrange(2,x): isItPrime = True for prime in primes: if (i%prime) == 0: isItPrime = False break if isItPrime: primes.append(i) print "Found a prime: "+str(i) sleep(0.0000001) print primes[-1] 

Código muy poco eficiente, esa no es la mejor manera de obtener divisores, lo he hecho con a for y range , pero no puedo ejecutarlo debido a las variables largas, así que decidí implementarlo con a por un tiempo, e incrementar un contador por mi mismo.

Para 32 bits int como 13195:

 # The prime factors of 13195 are 5, 7, 13 and 29. # What is the largest prime factor of the number 600851475143 ? i = 13195 for j in xrange(2, i, 1): if i%j == 0: i = i/j print j 

Buena manera para números más largos:

 # The prime factors of 13195 are 5, 7, 13 and 29. # What is the largest prime factor of the number 600851475143 ? i = 600851475143 j = 2 while i >= j: if i%j == 0: i = i/j print j j = j+1 

El último primo es el último valor impreso.