素数生成器中的段错误

Question

我知道下面这个方法不是生成质数列表最快的方式，但我自己想了这个问题，在上网查资料之前就写了这个程序。它在处理小于大约44,000的数字时运行得很好，但在我的2Ghz Core 2 Duo Macbook上，当处理更大的数字时就出现了“段错误”。我现在并不想了解其他方法，而是想知道为什么会出现段错误。

它能计算的最后一个质数是42751，然后就出错了，提示“段错误”。

from sys import argv, exit, setrecursionlimit

def isPrime(no, halfNo, x = 3):

  # if counted through and all numbers from 3 too x are not factors is prime
  if x > halfNo:
    print no
    return 1

  # is x a factor?
  if no % x == 0:
    return 0
  else:
    isPrime(no, halfNo, x + 2)

path, limLow, limHigh = argv

limLow = int(limLow)
limHigh = int(limHigh)

setrecursionlimit(limHigh)

# negitive numbers, 0 and 1 are not primes so answer invalid
if limLow < 2:
  exit('Invalid input');

# if lower limit is even its not prime so increase by 1
if limLow % 2 == 0:
  limLow += 1

while (limLow <= limHigh):
  isPrime(limLow, limLow / 2)
  limLow += 2

Answer 1

设置一个非常大的递归限制，然后进行很多次递归，是导致Python解释器崩溃的一个已知方法。

简单来说，就是你在告诉Python，如果你递归得太深，它不要阻止你，然后你就真的递归得太深了。

Answer 2

你的程序正在使用递归，也就是函数自己调用自己。每次调用函数时，程序会把一些信息保存在一个叫做“栈”的地方，然后再跳回函数的开头。因为这个栈的大小是有限的，所以最终会用完这个空间。到那时，你就可能会覆盖一些不该碰的内存区域，这样就会导致程序崩溃，出现“段错误”。

Answer 3

你可能会因为递归调用太多而导致栈溢出。在42751这个数字时，你的函数调用栈深度达到了21375层。在这种情况下，可能需要对你的方法进行一些调整。

你可以写一个简单的程序来检查一个数字是否是质数，代码大概是这样的（伪代码）：

if n < 2 return false;
if n == 2 or n == 3 return true;
if n % 2 == 0 return false;
if n % 3 == 0 return false;
for (i = 6; i < sqrt(n); i += 6) {
  if (n % (i - 1) == 0) return false;
  if (n % (i + 1) == 0) return false;
}
return true;

这个方法之所以有效，是因为：

1. 如果n小于2，那它就不可能是质数。
2. 如果n是2或3，那它一定是质数。
3. 如果n不是2或3，但能被其中一个整除，那它就不是质数。
4. 除了2和3以外的所有质数都可以表示成6k+1或6k-1的形式。如果一个数字是质数，它不能被任何其他质数整除。只需要检查到n的平方根，因为超过这个范围的数字肯定不能整除n。