python - 素数生成器中的段错误

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

您可能会因堆栈上的太多递归调用而导致堆栈溢出。在 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 的东西肯定不能平均分配给 n。