Python "OverflowError"

Question

Sto appena iniziando a imparare a codificare in Python. Sto cercando di scrivere del codice per rispondere a questa domanda Project Euler:

i fattori primi di 13195 sono 5, 7, 13 e 29.

Qual è il più grande fattore primo del numero 600.851.475.143?

mio programma funziona con il caso di test di 13195, ma quando provo ad entrare 600.851.475.143, ottengo l'errore: "OverflowError: range() risultati ha troppe voci" Qualcuno sa come posso risolvere questo problema?

Ecco il mio codice:

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 

Qualsiasi aiuto o suggerimenti sarebbe molto apprezzato!

Answer 1

Sto supponendo che stai usando python 2 e non python 3 - range(2,n) effettivamente costruisce una lista! Non hai abbastanza memoria per memorizzare 600 miliardi di numeri! xrange dovrebbe andare bene, però.

Inoltre, la tua idea di i=i-1 non funziona. I loop non funzionano come C, e questo hack funziona solo nei loop in stile C. Il ciclo for scorre su range(2,n). Se i ottiene il valore 5 in una sola volta, quindi indipendentemente da ciò che si fa a i, la successiva successiva sarà ancora 6.

Inoltre, l'elenco range(2,n) viene creato quando si accede al ciclo. Quindi quando modifichi n, questo non cambia nulla.

Dovrai ripensare la tua logica un po '.

(se non mi credete, provare a utilizzare 175 come un banco di prova)

Come ultimo commento, probabilmente si dovrebbe prendere l'abitudine di usare la divisione speciale intero: n = n // i. Anche se / e // funzionano allo stesso modo in python 2, questo è un comportamento deprecato e non funzionano lo stesso in python 3, dove / ti darà un numero in virgola mobile.

Answer 2

È possibile risolvere il problema utilizzando xrange invece di range

vostro prossimo problema sarà che il programma prende troppo tempo per eseguire perché è necessario uscire dal giro in alcune condizioni

A modo migliore per affrontare i fattori di ripetizione è di sostituire il if con un while

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

Answer 3

la funzione range crea un elenco e TR per memorizzarlo. La creazione di un elenco di molti numeri è ciò che sta causando OverflowError. È possibile utilizzare xrange per ottenere un generatore che produce i numeri su richiesta.

Detto questo, penso che troverete che il vostro algoritmo è troppo lento per il calcolo di numeri primi grandi. Esistono molti algoritmi di numeri primi, ma potrei suggerire di verificare lo Sieve of Eratosthenes come punto di partenza.

MODIFICA: Correttamente xrange in realtà non restituisce un generatore, ma un oggetto xrange che si comporta molto come un generatore. Non sono sicuro che ti interessi, ma mi ha infastidito il fatto che non ero preciso!

Answer 4

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

Penso che si può ottimizzare la funzione notando che

for i in range(2,n): 

è possibile sostituire

range(2,n) 

da

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

perché, si può vedere wiki ..

Answer 5

Stavo combattendo con questo Python "OverflowError", anche, lavorando a questo progetto. Mi stava facendo impazzire cercando di trovare una combinazione che funzionasse.

Tuttavia, ho scoperto un ingegnoso, almeno penso di sì :), modo di farlo.

Ecco il mio codice per questo 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 

Quello che ho fatto è stato prendere i fattori del numero inserito e inserirli in una lista "fattori". Successivamente, prendo la lista dei fattori e stabilisco quali sono i numeri primi e li memorizziamo in una lista, che viene stampata.

Spero che questo aiuta

- Mike

Answer 6

Questo è il modo migliore per trovare i numeri primi che ho trovato finora:

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

Questo mi ci sono voluti circa 5 secondi per ottenere la risposta.

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 probabilmente non aiuterà a (o può!), Ma la cosa fondamentale è quello di reliaze che non c'è bisogno di trovare i numeri primi fino ad 600.851.475.143 o fattori di 600.851.475.143, ma è fattori primi, quindi ... Utilizzare il buon metodo primo fattorizzazione vecchio, in questo modo:

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) 

Ciò restituirà il fattore principale argest quasi istantaneamente