python - python 3.x 中的递归 is_prime 函数

Question

在我学校的计算机科学 2 类(class)中，我们目前正在探索递归。我们已经使用递归来做诸如阶乘或斐波那契数列之类的事情，但仍然停留在 is_prime(n) 函数上，如果 n 是素数则返回 True，否则返回 False。我们之前迭代地写了一个，但似乎无法弄清楚如何递归地做它。这是我们目前所拥有的:

def is_prime(n):

    if n < 2: return False
    #1 or 0 is not prime, base case 1

    if n == 2 or n == 3: return True
    #2 and 3 are both prime, base case 2

    if is_prime(n-1): return False
    #This checks if n-1 is prime, b/c if so then n must not be prime
    #However, this only works b/c the first few numbers have lots of primes

    return True
    #Only returns True if nothing else has returned

如果有人可以帮助我们一点点，最好是通过一些提示，那就太好了。谢谢!

Answer 1

is_prime(n-1) 对计算 is_prime(n) 不是很有帮助。相反，递归方法将在辅助函数中进行递归，该辅助函数完成大部分计算。

类似 no_divisors(n,k) 如果范围 2, 3, ..., k 不包含则计算结果为 True n 的除数。很容易看出 no_divisors(n,k) 可以简化为 no_divisors(n,k-1)。定义此函数，然后根据它定义 is_prime()。作为一种优化，您可能希望首先检查可被 2 和 3 整除作为基本情况，然后只查看奇数候选除数。