How to handle big numbers in python

Question

My problem is to find the largest prime factor of 600851475143.

Code:

class Prime:
    def isPrime(self,n): # Checks if number is prime
        number=n        
        flag=0
        #code to exclude 1 nd 2 from check
        if number==1:
            return False
        elif number==2:
            return True
         #code to loop through and check if number is divisible    
        for i in range(2,(number/2)+1):
            if (number)%i==0:
                flag=1
                break
            else:
                flag-0
                continue 
        #code to return result   

        if flag==0:
            return True
        elif flag==1:
            return False

But this code throws an overflow error - "OverflowError: range() result has too many items". What can I do to handle a big number?

I tried using n = int(raw_input()) as suggested in "Python long integer input", but no luck!

def main():
    p=Prime()
    n = int(raw_input())
    print p.isPrime(n)

Prune · Answer 1 · 2017-05-24T15:57:24.780

The problem is the quantity of numbers, not the size. You build a range object for 600851475143/2 elements. Single-word integers alone would consume over a terabyte of memory for this. Since you're using large integers, you consume even more memory. Just how much address space do you have?

Reduce the size of the needed elements. First of all, you need check only through the square root of the number to complete the prime factorization. Second, you don't have to build a generator: just increment a variable, eliminating the structure entirely. Finally, you need divide by primes only, not all numbers.

First step:

for i in range(2, int(math.sqrt(number))+1):
    while number % i == 0:
        number = number // i
        largest = i

When you're done, the largest prime factor is the greater of number and largest.

Second step:

Convert that large range expression to a simple variable increment:

i = 2
upper = int(math.sqrt(number) + 1)
while i < upper:
    while number % i == 0:
        number = number // i
        largest = i
    i +=1

You can speed this up 2x by doing only 2 and then the odd numbers.

Algorithm improvement:

Build a sieve, or other method to keep track of primes. Iterate through those instead of through all integers.

Switching `range()` for `xrange()` would use less memory too. — Mikael, May 23 '17 at 18:28
Most of this is 'how to write more efficient factorization' rather than addressing the immediate (and trivially avoidable) problem of needlessly creating a giant in-memory collection of integers. — pvg, May 24 '17 at 01:12

How to handle big numbers in python

1 Answers1