素数生成中的分段错误

Question

我知道下面的方法不是生成素数列表的最快方法，但是在google上写下这个程序之前，我给自己提出了这个问题。它适用于数字约44000，但在我的2Ghz Core 2 Duo Macbook上运行时会出现分段错误。我现在对其他方法不感兴趣，但我对为什么它会给我一个seg错误感兴趣。在

在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

你的程序正在使用递归。每个函数调用都将寄存器保存到堆栈上，然后跳到函数的开头。由于堆栈的大小是有限的，最终将耗尽堆栈空间。在这一点上，你就是在写你不应该（甚至不允许）的记忆。从而导致分割错误。在

Answer 2

堆栈上重复调用太多可能会导致堆栈溢出。在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

Answer 3

设置一个非常大的递归限制，然后递归一个束是使Python interpeter崩溃的documented方法之一。在

实际上，您是在告诉Python，如果递归太远，就不要停止，然后递归太远。在