我知道以下不是生成素数列表的最快方法,但是我给自己提出了这个问题,并且在谷歌搜索之前编写了以下程序。对于 < ~ 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
最佳答案
您可能会因堆栈上的重复调用过多而导致堆栈溢出。在 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;
此方法有效的原因如下:
- 如果 n 小于 2,则它不可能是素数
- 如果 n 是 2 或 3,则它必须是素数
- 如果 n 不是 2 或 3,但可以被其中任何一个整除,则它不是素数
- 除了 2 和 3 之外的所有素数都可以写成 6k+1 或 6k-1 的形式。如果一个数是素数,则它不能被任何其他素数整除。只需要检查直到 n 的平方根,因为超过这个值的任何东西都肯定不能被 n 整除。
关于python - 素数生成器中的段错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3885793/