Python"OverflowError"

Question

我刚开始学习用Python编写代码.我正在尝试编写一些代码来回答这个Project Euler问题:

13195的主要因素是5,7,13和29.

600851475143的最大主要因素是什么？

我的程序适用于13195的测试用例,但是当我尝试输入600851475143时,我收到错误:"OverflowError:range()结果有太多项目"有谁知道如何解决这个问题？

这是我的代码:

class Euler3:
    "A class to find the largest prime factor of a given number"
     n = 600851475143
     primeFactors = []
     for i in range(2,n):
         if (n%i ==0):
            primeFactors.append(i)
            n = n/i
            i = i -1 #reset i
     print primeFactors

任何帮助或建议将不胜感激!

Answer 1

该range函数创建一个列表并尝试将其存储在内存中.创建一个很长的列表是造成OverflowError的原因.您可以xrange改为使用生成按需生成数字的生成器.

也就是说,我认为你会发现你的算法对于计算大质数而言太慢了.有许多素数算法,但我可能会建议将Eratosthenes筛选作为起点.

编辑:正确地xrange实际上不返回生成器,而是一个xrange对象,其行为很像生成器.我不确定你是否在乎,但这让我觉得我不准确!

Answer 2

我猜你使用的是 python 2 而不是 python 3 ——range(2,n)实际上构建了一个列表！你没有足够的内存来存储 6000 亿个数字！xrange不过应该没问题。

另外，你的想法i=i-1行不通。For 循环不像 C 那样工作，而且这个 hack 只适用于 C 风格的循环。for 循环迭代range(2,n). 如果在一次迭代中i获得值5，那么无论您对 做什么i，它仍然会6在下一次迭代中获得。

此外，该列表range(2,n)是在进入循环时构建的。因此，当您修改 时n，不会改变任何内容。

你将不得不重新思考一下你的逻辑。

（不信的话可以尝试用175作为测试用例）

作为最后的评论，您可能应该养成使用特殊整数除法的习惯：n = n // i。虽然/和//在 python 2 中工作方式相同，但这确实是不推荐的行为，并且它们在 python 3 中工作方式不同，其中/会给你一个浮点数。