Python "OverflowError"

I am just starting to learn to code in Python. I am trying to write some code to answer this Project Euler Question:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My program works with the test case of 13195, but when I try to enter 600851475143, I get the error: "OverflowError: range() results has too many items" Does anyone know how I can fix this?

Here is my code:

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

Any help or suggestions would be much appreciated!

python overflow

Edit Report

I'm guessing you're using python 2 and not python 3 -- range(2,n) actually constructs a list! You don't have enough memory to store 600 billion numbers! xrange should be fine, though.

Also, your idea of i=i-1 doesn't work. For loops don't work like C, and that hack only works in C-style loops. The for loop iterates over range(2,n). If i gets the value 5 at once iteration, then no matter what you do to i, it still gets 6 the next time through.

Also, the list range(2,n) is constructed when you enter the loop. So when you modify n, that doesn't change anything.

You're going to have to rethink your logic a bit.

(if you don't believe me, try using 175 as a test case)

As a last comment, you should probably get in the habit of using the special integer division: n = n // i. Although / and // work the same in python 2, that is really deprecated behavior, and they don't work the same in python 3, where / will give you a floating point number.

answered 2012-05-28T02:38:56.990

1 Answer

Your Answer