以更好的方式检查质数以绕过最大递归深度

Question

我有一个递归函数来检查输入的值是否为质数。但是，此代码在大约1000时不再起作用，并引发错误“ RecursionError：超出最大递归深度”。这是我的代码：

def is_prime(a,N):
    print(a, N)
    if N <= 1:
        return 
    else:
        if a >= N:
            print(N)
        else:
            if N == 2: 
                print(N)
            elif (N % a) == 0:
                return False
            else:
                return is_prime(a+1,N)

    return False

所以我想知道，还有另一种方法可以更有效地检查素数，这样我就不会再出现此错误？我听说有某种平方方法，但我不确定如何实现。

Answer 1

尝试实现非递归版本：

def is_prime(n):
    for i in range(3, int(n ** 0.5 + 1), 2):
        if n % i == 0:
            return False
    return True