python "OverflowError"

Question

我刚开始学习用 Python 编写代码。我正在尝试编写一些代码来回答这个欧拉项目问题:

13195 的质因数是 5、7、13 和 29。

数 600851475143 的最大质因数是多少？

我的程序适用于 13195 的测试用例，但是当我尝试输入 600851475143 时，出现错误:“OverflowError: range() results has too many items”有谁知道我该如何解决这个问题？

这是我的代码:

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 来获得按需生成数字的生成器。

也就是说，我认为您会发现您的算法对于计算大素数来说太慢了。有很多素数算法，但我可能建议查看 Sieve of Eratosthenes作为起点。

编辑:xrange 实际上并不返回一个生成器，而是一个行为很像生成器的 xrange 对象。我不确定你是否在乎，但我不准确让我很烦恼!