首页 文章

使用python计算最大素因子时的内存错误

提问于
浏览 次
1

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

回溯（最近一次调用最后一次）：文件“prb3.py”，第45行，在print prime_factor（）文件“prb3.py”，第12行，在prime_factor中为n在范围（2，i）中：MemoryError

当我使用像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()
python

1 回答

  • 3

    在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次可以使您的程序更快

    回复于

相关问题