Range is too large Python

Question

I'm trying to find the largest prime factor of the number x, Python gives me the error that the range is too large. I've tried using x range but I get an OverflowError: Python int too large to convert to C long

x = 600851475143
maxPrime = 0


for i in range(x):
    isItPrime = True
    if (x%i == 0):
        for prime in range(2,i-1):
            if (i%prime == 0):
                isItPrime = False
        if (isItPrime == True):

            if (i > maxPrime):
                maxPrime = i;

print maxPrime

Answer 1

In old (2.x) versions of Python, xrange can only handle Python 2.x ints, which are bound by the native long integer size of your platform. Additionally, range allocates a list with all numbers beforehand on Python 2.x, and is therefore unsuitable for large arguments.

You can either switch to 3.x (recommended), or a platform where long int (in C) is 64 bit long, or use the following drop-in:

import itertools
range = lambda stop: iter(itertools.count().next, stop)

Equivalently, in a plain form:

def range(stop):
   i = 0
   while i < stop:
       yield i
       i += 1

Answer 2

This is what I would do:

def prime_factors(x):
    factors = []
    while x % 2 == 0:
        factors.append(2)
        x /= 2
    i = 3
    while i * i <= x:
        while x % i == 0:
            x /= i
            factors.append(i)
        i += 2
    if x > 1:
        factors.append(x)
    return factors

>>> prime_factors(600851475143)
[71, 839, 1471, 6857]

It's pretty fast and I think it's right. It's pretty simple to take the max of the factors found.

---

2017-11-08

Returning to this 5 years later, I would use yield and yield from plus faster counting over the prime range:

def prime_factors(x):
    def diver(x, i):
        j = 0
        while x % i == 0:
            x //= i
            j += 1
        return x, [i] * j
    for i in [2, 3]:
        x, vals = diver(x, i)
        yield from vals
    i = 5
    d = {5: 2, 1: 4}
    while i * i <= x:
        x, vals = diver(x, i)
        yield from vals
        i += d[i % 6]
    if x > 1:
        yield x

list(prime_factors(600851475143))

The dict {5: 2, 1: 4} uses the fact that you don't have to look at all odd numbers. Above 3, all numbers x % 6 == 3 are multiples of 3, so you need to look at only x % 6 == 1 and x % 6 == 5, and you can hop between these by alternately adding 2 and 4, starting from 5.