Python "OverflowError"

Question

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!

Answer 1

The range function creates a list and tries to store it in memory. Creating a list many numbers long is what's causing the OverflowError. You can use xrange instead to get a generator which produces the numbers on demand.

That said, I think you'll find that your algorithm is way too slow for calculating large primes. There are a lot of prime number algorithms, but I might suggest checking out the Sieve of Eratosthenes as a starting point.

EDIT: Properly xrange actually doesn't return a generator, but an xrange object which behaves a lot like a generator. I'm not sure if you care, but it was bugging me that i wasn't precise!

Answer 2

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.

Answer 3

You can fix the problem by using xrange instead of range

Your next problem will be that the program takes way too long to run because you need to break out of the loop under some condition

A better way to deal with repeat factors is to replace the if with a while

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

Answer 4

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

i think you can optimize the function by noticing that

for i in range(2,n):

you can replace

range(2,n)

by

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

because, you can see wiki...

Answer 5

This is the best way to find primes that I've found so far:

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 6

This took me about 5 secs to get the answer.

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 7

xrange won't probably help you(or it may!),but the key thing here is to reliaze that you don't need to find the prime numbers up till 600851475143 or the factors of 600851475143,but it's prime factors,so... Use the good old prime factorization method ,like so:

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)

This will return the argest prime factor almost instantly

Answer 8

I was battling with this Python "OverflowError", as well, working on this project. It was driving me nuts trying to come up with a combination that worked.

However, I did discover a clever, at least I think so :), way to do it.

Here is my code for this problem.

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

What I did was take the factors of the number entered and enter them into a list "factors". After that, I take the list of factors and determine which ones are primes and store them into a list, which is printed.

I hope this helps

-- Mike