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!

Solution 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!

Solution 2

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

Solution 3

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

Solution 4

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)

Solution 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

View more solutions