Python "OverflowError"

Question

Estoy empezando a aprender a codificar en Python. Estoy tratando de escribir algo de código para responder a esta pregunta Proyecto Euler:

Los factores primos de 13195 son 5, 7, 13 y 29.

¿Cuál es el mayor factor primo del número 600 851 475 143?

Mi programa funciona con el caso de prueba de 13195, pero cuando intento ingresar 600851475143, aparece el error: "OverflowError: range() results tiene demasiados elementos" ¿Alguien sabe cómo puedo solucionar esto?

Aquí está mi código:

class Euler3: 
    "A class to find the largest prime factor of a given number" 
    n = 600851475143 
    primeFactors = [] 
    for i in range(2,n): 
     if (n%i ==0): 
      primeFactors.append(i) 
      n = n/i 
      i = i -1 #reset i 
    print primeFactors 

Cualquier ayuda o sugerencia sería muy apreciada!

Answer 1

Supongo que estás usando python 2 y no Python 3 - range(2,n) ¡realmente construye una lista! ¡No tienes suficiente memoria para almacenar 600 mil millones de números! xrange debería estar bien, sin embargo.

Además, su idea de i=i-1 no funciona. Para los bucles no funcionan como C, y ese truco solo funciona en bucles tipo C. El ciclo for itera sobre range(2,n). Si i obtiene el valor 5 en iteración, no importa lo que haga en i, todavía obtiene 6 la próxima vez.

Además, la lista range(2,n) se genera cuando ingresa al bucle. Entonces cuando modificas n, eso no cambia nada.

Tendrás que reconsiderar tu lógica un poco.

(si no me cree, trate de usar 175 como un caso de prueba)

Como último comentario, probablemente debería tener el hábito de usar la división entera especial: n = n // i. Aunque / y // funcionan igual en python 2, eso es realmente un comportamiento obsoleto, y no funcionan igual en python 3, donde / le dará un número de punto flotante.

Answer 2

Puede solucionar el problema mediante el uso de xrange en lugar de range

Su siguiente problema será que el programa toma demasiado tiempo para correr porque es necesario para romper el bucle de bajo alguna condición

Un mejor manera de hacer frente a los factores de repetición es reemplazar el if con un while

 while (n%i ==0): 
     primeFactors.append(i) 
     n = n/i 

Answer 3

la función range crea una lista y tr es para almacenarlo en la memoria. Crear una lista de muchos números es lo que causa OverflowError. Puede usar xrange en su lugar para obtener un generador que produce los números a pedido.

Dicho esto, creo que encontrará que su algoritmo es demasiado lento para calcular números primos grandes. Hay muchos algoritmos de números primos, pero podría sugerir revisar el Sieve of Eratosthenes como punto de partida.

EDITAR: Correctamente xrange en realidad no devuelve un generador, sino un objeto xrange que se comporta mucho como un generador. No estoy seguro si te importa, ¡pero me molestaba que no fuera preciso!

Answer 4

n = 600851475143 
primeFactors = [] 
for i in range(2,n): 

Creo que se puede optimizar la función observando que

for i in range(2,n): 

se puede reemplazar

range(2,n) 

por

range(2,int(sqrt(n))+2) 

porque, se puede ver wiki ..

Answer 5

Estaba luchando con este "OverflowError" de Python, también, trabajando en este proyecto. Me estaba volviendo loco intentar una combinación que funcionara.

Sin embargo, descubrí una forma inteligente, al menos eso creo :), de hacerlo.

Aquí está mi código para este problema.

def IsNumberPrime(n): 
    bounds = int(math.sqrt(n)) 
    for number in xrange(2,bounds+2): 
     if n % number == 0: 
      return False 
    return True 

def GetListOfPrimeFactors(n): 
    primes = [] 
    factors = GetListOfFactors(n) 
    if n % 2 == 0: 
     primes.append(2) 

    for entries in factors: 
     if IsNumberPrime(entries): 
      primes.append(entries) 
    return primes 


GetListOfPrimeFactors(600851475143) 

def GetListOfFactors(n): 
    factors = [] 
    bounds = int(math.sqrt(n)) 
    startNo = 2 

    while startNo <= bounds: 
     if n % startNo == 0: 
     factors.append(startNo) 
     startNo += 1 
    return factors 

Lo que hice fue tomar los factores del número introducido e introducirlos en una lista de "factores". Después de eso, tomo la lista de factores y determino cuáles son primos y los almaceno en una lista, que se imprime.

espero que esto ayude a

- Mike

Answer 6

Ésta es la mejor manera de encontrar números primos que he encontrado hasta ahora:

def isprime(n): 
    #make sure n is a positive integer 
    n = abs(int(n)) 
    #0 and 1 are not primes 
    if n < 2: 
     return False 
    #2 is the only even prime number 
    if n == 2: 
     return True 
    #all other even numbers are not primes 
    if not n & 1: 
     return False 
    #range starts with 3 and only needs to go up to the square root of n 
    #for all odd numbers 
    for x in range (3, int(n**0.5)+1, 2): 
     if n % x == 0: 
      return False 
    return True #if it makes it through all the catches, it is a prime 

Answer 7

Esto me llevó a unos 5 segundos para llegar la respuesta.

import math 

def is_prime_number(x): 
    for i in range(int(math.sqrt(x)), 2, -1): 
     if x % i == 0: 
     return False 
    return True 

def next_prime_number(number): 
    #Returns the next prime number. 
    if number % 2 == 0 and number != 2: 
     number += 1 
    while not is_prime_number(number): 
     number += 2 
    return number 

num = 600851475143 
i = 2 
while (i < long(math.sqrt(num)/2)): 
    if num % i == 0: 
     largest = i 
     print largest 
    i = next_prime_number(i + 1) 

Answer 8

xrange no es probable que le ayude (o puede!), Pero la clave aquí es que reliaze que no es necesario para encontrar los números primos hasta el 600 851 475 143 o 600 851 475 143 de los factores, pero es los factores primos, así que ... Utilice el buen método factorización prima de edad, así:

A=600851475143 
n=2 
fac=[] 
while(n<=int(A)): 
    B=1 
    while(A%n==0): 
     B=0 
     A=A/n 
    if(B==0): 
     fac.append(n) 
    n=n+1 

print max(fac) 

Esto devolverá el factor primordial argest casi instantáneamente