python 3.x 中的递归 is_prime 函数

Question

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

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

也许递归另一个值并反复检查你的 n 不是那个值的倍数？像这样：

从 d 开始作为上限

1) 如果 d 已达到下限 - return false

2) 如果 n 是 d 的倍数 - return true

3) 默认情况 - 通过递减 d

递归

您可以选择下限和上限的含义。（例如从 2 到 n/2 是最基本的方法）

另一种可能的下限方法是将 d 从 sqrt(n) 递归到 2，甚至预先检查除以 2 并跳过一些值等...

Answer 2

确定素数的一种简单方法是测试区间 [2, sqrt(n)] 中的所有整数 x 是否 n % x == 0。要递归地执行此操作：

在 2

x

检查是否 n % x == 0
如果不是，递增 x 并再次调用 is_prime 函数
如果n < x * x那么n是质数

Answer 3

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

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

python 3.x 中的递归 is_prime 函数

Recursive is_prime function in python 3.x

python

recursion

primes

python-3.x