我刚开始学习用 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
如有任何帮助或建议,我们将不胜感激!
最佳答案
range
函数创建一个列表并尝试将其存储在内存中。创建一个很多数字长的列表是导致 OverflowError 的原因。您可以改用 xrange
来获得按需生成数字的生成器。
也就是说,我认为您会发现您的算法对于计算大素数来说太慢了。有很多素数算法,但我可能建议查看 Sieve of Eratosthenes作为起点。
编辑:xrange
实际上并不返回一个生成器,而是一个行为很像生成器的 xrange 对象。我不确定你是否在乎,但我不准确让我很烦恼!
关于 python "OverflowError",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10778764/