Memory error while calculating largest prime factor using python

Question

I am trying to find out largest prime number of a big number, when I run this I run into an error saying:

Traceback (most recent call last): File "prb3.py", line 45, in print prime_factor() File "prb3.py", line 12, in prime_factor for n in range(2,i): MemoryError

It works fine when I run with small number like 13195

"""
Problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
"""
import math
def prime_factor():
        i=600851475143
        factors=[] #list stores all the factors of a number
        for n in range(2,i):
                if(i%n==0 and (n%2!=0 and n!=2)):
                        factors.append(n)

        """
        Now I have all the factors(which are not even numbers)

        Next step is to find prime number from factors list
        """

        for factor in factors:
                sqr_root=int(math.sqrt(factor))
                """
                I take a factor from list and divide it by numbers from 3
                to sqroot(factor-1).If I get a 0 as remainder I consider it
                as non prime and remove from the list.I apply this only to
                factors whose sqr root is greater than 3.If it is less than 
                3 I divide it by each number between 3 and factor-1.
                """
                if(sqr_root<=3):
                        for num in range(3,factor-1):
                                if(factor%num==0):
                                        factors.remove(factor)
                                        break
                else:
                        for num in range(3,sqr_root):
                                if(factor%num==0):
                                                                                                                            1,1           Top
        return len(factors)


if __name__ == "__main__":
        print prime_factor()

Answer 1

In Python2, range() returns a list. In your case the list would contain 600851475141 int objects. Since the list is so big, it can't fit in your memory so you get that memory error

Since you don't really need all those numbers in memory at the same time, you could try using xrange() instead.

I think you can simplify your problem by dividing out the factors as you find them. eg.

    for n in xrange(2, i):
        while(i % n == 0 and (n % 2 != 0 and n != 2)):
            i /= n
            print n
        if i == 1:    
            break

Not needing to loop 600851475141 times should make your program much faster