interval - El rango es demasiado grande para Python

range python 3

Question

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

Answer 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.

Answer 2

Definitivamente me quedaría con xrange ya que crear una lista entre 0 y lo que parece un número que rivaliza con el infinito sería un gravamen 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 programa 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 programa 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]

Answer 3

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 menú desplegable:

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

Answer 4

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 estos agregando alternativamente 2 y 4, a partir del 5.

Answer 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