python - 使用python计算最大素因数时出现内存错误

Question

我试图找出一个大数的最大素数，当我运行这个时，我遇到一个错误:

回溯(最近一次调用最后一次): 文件“prb3.py”，第 45 行，位于 打印素数因子() 文件“prb3.py”，第 12 行，在 prime_factor 中 对于范围 (2,i) 中的 n:内存错误

当我运行像 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

在Python2中，range()返回一个列表。在您的情况下，列表将包含 600851475141 int 对象。由于列表太大，它无法容纳在您的内存中，因此您会收到内存错误

由于您实际上并不需要同时在内存中存储所有这些数字，因此您可以尝试使用 xrange() 来代替。

我认为您可以通过划分找到的因素来简化您的问题。例如。

    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

不需要循环 600851475141 次应该会让你的程序更快