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

Question

在我学校的计算机科学 2 课上，我们目前正在探索递归。我们已经使用递归来完成阶乘或斐波那契数列之类的事情，但被困在 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 整除作为基本情况，然后只查看奇数候选除数。