Python的“OverflowError”

Question

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

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

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

- stk1234

---

你做错了。对于每个因子 x，都有另一个因子 y，使得 x*y = num。如果 x 是第 n 小的因子，则 y 将是第 n 大的因子（证明留给读者作为练习）。找到最小的因子 x，然后执行 y = num/x。如果 y 是质数，则它就是你要找的数字，否则继续执行。此外，可以证明 x 比 sqrt(num) 小，因此可以缩小 range() 的范围。 - WhyNotHugo

Answer 1

range函数会创建一个列表并尝试将其存储在内存中。创建一个很长的数字列表会导致OverflowError（溢出错误）。你可以使用xrange来获取生成器，该生成器按需生产数字。

话虽如此，我认为你会发现你的算法对于计算大质数而言速度太慢了。有很多质数算法，但我建议从埃拉托色尼筛法入手。

编辑：实际上xrange不会返回生成器，而是返回一个类似于生成器的xrange对象。我不确定你是否在意，但这让我感到不精确！

- Julian

---

非常感谢！这是有帮助的信息。我刚查了一下厄拉多塞筛法，目前正在进行第二次草稿。感谢您抽出时间回答我的问题！ - stk1234

Answer 2

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

此外，您的i = i-1的想法行不通。for循环不像C语言那样工作，那种黑客方式只在C样式循环中有效。for循环迭代range(2,n)。如果在一个迭代中i得到5的值，那么无论你对i做什么，下一次迭代它仍然得到6。

另外，列表range(2,n)在进入循环时构建。因此，当你修改时，这并没有改变任何东西。

你需要重新考虑你的逻辑。

（如果你不相信我，请尝试使用175作为测试用例）

最后，您应该养成使用特殊整数除法的习惯：n = n // i。虽然在Python 2中，/和//的作用是相同的，但这种行为已经被弃用，在Python 3中它们的作用是不同的，其中/将给你一个浮点数。

- user1084944

---

感谢您对for循环的评论。我的主要编程语言是Java，它与C有很多相似之处，例如您可以通过i = i - 1来重置循环。很高兴知道这在Python中是不起作用的。谢谢！ - stk1234

Answer 3

你可以使用xrange代替range来解决问题。

下一个问题是程序运行时间太长，需要在某些条件下跳出循环。

更好的处理重复因素的方法是将if替换为while。

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

- John La Rooy

---

在这种情况下，当她修复逻辑时，她会很幸运，它会很快完成。 - user1084944

Answer 4

n = 600851475143
primeFactors = []
for i in range(2,n):

我认为您可以通过注意以下内容来优化该函数。

for i in range(2,n):

你可以替换 < /p>

range(2,n)

by

range(2,int(sqrt(n))+2)

因为，你可以看到维基百科...

- kaitian521

Answer 5

这是我目前发现的找到质数的最佳方法：

def isprime(n):
    #make sure n is a positive integer
    n = abs(int(n))
    #0 and 1 are not primes
    if n < 2:
        return False
    #2 is the only even prime number
    if n == 2:
        return True
    #all other even numbers are not primes
    if not n & 1:
        return False
    #range starts with 3 and only needs to go up to the square root of n
    #for all odd numbers
    for x in range (3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True #if it makes it through all the catches, it is a prime

- Blairg23

Answer 6

这句话的意思是“我花了大约5秒钟就得到了答案”，其中保留了HTML标记。

import math

def is_prime_number(x):
   for i in range(int(math.sqrt(x)), 2, -1):
      if x % i == 0:
        return False
   return True

def next_prime_number(number):
    #Returns the next prime number.
    if number % 2 == 0 and number != 2:
        number += 1
    while not is_prime_number(number):
        number += 2
    return number

num = 600851475143
i = 2
while (i < long(math.sqrt(num) / 2)):
    if num % i == 0:
       largest = i
       print largest
    i = next_prime_number(i + 1)

- chinmay

Answer 7

xrange可能对你没有帮助（或者也许有用！），但这里的关键是要意识到你不需要找到600851475143以内的质数或因子，而是它的质因数，所以要使用好老旧的质因数分解方法，像这样：

A=600851475143
n=2
fac=[]
while(n<=int(A)):
    B=1
    while(A%n==0):
        B=0   
        A=A/n
    if(B==0):
        fac.append(n)
    n=n+1

print max(fac)

这将几乎立即返回最大的质因数。

- arkin

Answer 8

我在处理这个Python的"OverflowError"时，也在进行这个项目。试图找到一个可行的组合让我感到非常困扰。

然而，我发现了一种聪明的方法，至少我认为是聪明的：）

以下是我解决这个问题的代码。

def IsNumberPrime(n):
   bounds = int(math.sqrt(n))
   for number in xrange(2,bounds+2):
        if n % number == 0:
            return False
   return True

def GetListOfPrimeFactors(n):
    primes = []
    factors = GetListOfFactors(n)
    if n % 2 == 0:
       primes.append(2)

    for entries in factors:
       if IsNumberPrime(entries):
          primes.append(entries)
    return primes


GetListOfPrimeFactors(600851475143)

def GetListOfFactors(n):
   factors = []
   bounds = int(math.sqrt(n))
   startNo = 2

   while startNo <= bounds:
      if n % startNo == 0:
         factors.append(startNo)
      startNo += 1
   return factors

我所做的是将输入数字的因子放入一个名为“factors”的列表中。然后，我将因子列表中的质数筛选出来并存储到另一个列表中，最后将其打印输出。

希望这能有所帮助。

-- Mike

- Mike