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.

Answer 3

The accepted answer suggests a drop-in replacement for xrange, but only covers one case. Here is a more general drop-in replacement.

def custom_range(start=0,stop=None,step=1):
    '''xrange in python 2.7 fails on numbers larger than C longs.
    we write a custom version'''
    if stop is None:
        #handle single argument case. ugly...
        stop = start
        start = 0
    i = start
    while i < stop:
        yield i
        i += step

xrange=custom_range

Answer 4

I would definitely stick with xrange since creating a list between 0 and what looks like a number rivaled by infinity would be taxing for memory. xrange will generate only the numbers when asked. For the number too large problem, you might want to try a "long". This can be achieved by writing a L on the end of the number. I made my own version to test it out. I put in a small sleep as to not destroy my computer into virtually a while(1) loop. I was also impatient to see the program come to a complete end, so I put in print statements

from time import sleep

x = 600851475143L
maxPrime = 0

for i in xrange(1,x):
    isItPrime = True
    if (x%i) == 0:
        for prime in xrange(2,i-1):
            if (i%prime) == 0:
                isItPrime = False
                break
        if isItPrime:
            maxPrime = i
            print "Found a prime: "+str(i)
    sleep(0.0000001)


print maxPrime

Hope this helps!

EDIT: I also did a few more edits to yield this version. It is fairly efficient and I checked quite a few numbers this program provides (it seems to check out so far):

from time import sleep

x = 600851475143L

primes = []

for i in xrange(2,x):
    isItPrime = True
    for prime in primes:
        if (i%prime) == 0:
            isItPrime = False
            break
    if isItPrime:
        primes.append(i)
        print "Found a prime: "+str(i)
    sleep(0.0000001)


print primes[-1]

Answer 5

Very uneficient code, that's not the best way of getting dividers, I've done it with a for and range, but I can't execute it because of the long variables, so I decided to implement it with a for using a while, and increment a counter by myself.

For 32 bit int like 13195:

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

i = 13195
for j in xrange(2, i, 1):
    if i%j == 0:
        i = i/j
        print j

Good way for longer numbers:

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

i = 600851475143
j = 2

while i >= j:
    if i%j == 0:
        i = i/j
        print j
    j = j+1

The last prime is the last printed value.

Answer 6

Another implementation for python 2 range():

import itertools
import operator

def range(*args):
    """Replace range() builtin with an iterator version."""
    if len(args) == 0:
        raise TypeError('range() expected 1 arguments, got 0')
    start, stop, step = 0, args[0], 1
    if len(args) == 2: start, stop = args
    if len(args) == 3: start, stop, step = args
    if step == 0:
        raise ValueError('range() arg 3 must not be zero')
    iters = itertools.count(start, step)
    pred = operator.__ge__ if step > 0 else operator.__le__
    for n in iters:
        if pred(n, stop): break
        yield n