Python“溢出错误”

Question

我刚刚开始学习用Python编写代码。我正试图编写一些代码来回答这个项目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

我猜您使用的是Python2，而不是Python3——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中的工作方式也不同，在python3中，/将给您一个浮点数。

Answer 2

函数range创建一个列表并尝试将其存储在内存中。创建一个许多数字长的列表是导致溢出错误的原因。您可以使用xrange来获得按需生成数字的生成器。

也就是说，我想你会发现你的算法对于计算大素数来说太慢了。有很多素数算法，但我可能建议从Sieve of Eratosthenes开始。

编辑：正确地xrange实际上并不返回生成器，而是返回一个行为非常类似生成器的xrange对象。我不确定你是否在乎，但我不太清楚，这让我心烦！

Answer 3

您可以使用xrange而不是range来解决问题

下一个问题是程序运行时间太长，因为在某些情况下需要中断循环

处理重复因子的更好方法是用while替换if

     while (n%i ==0):
        primeFactors.append(i)
        n = n/i