如何在 Python 中使用递归找到质数

Question

我必须使用递归找出 number(N) 是否为质数，不允许循环。我已经尝试将使用 for 循环的常用代码转换为递归代码，但它的行为并不相同。这个函数包含在另一个函数中，它是另一个函数的一部分。只应使用和传递参数 a 和 N 这是我的功能。

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

return

我相信这个错误就在这里。

elif (N % a) == 0:
            prime = False
            return is_prime(a+1,N)
        else:
            prime = True
            print(N)

这是我尝试转换的代码。

if num > 1:
   for i in range(2,num):
      if (num % i) == 0:
         print(num,"is not a prime number")
         print(i,"times",num//i,"is",num)
         break
   else:
      print(num,"is a prime number")

else:
   print(num,"is not a prime number")

Answer 1

您的解决方案已经很接近了，只需进行一些更改即可使其生效。

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

您没有给出任何调用此函数的示例，但我假设它总是在 a 为 2 的情况下被调用，因为任何其他值都没有意义。所以如果你运行上面的函数像这样，你应该得到正确的输出：

print(is_prime(2, 7))  => True
print(is_prime(2, 4))  => False
print(is_prime(2, 37)) => True

我认为您对递归的工作原理有误解，您在函数体中分配了这个 prime 变量，但从未对其进行任何操作。也许您的困惑来自对 Python 范围的误解。 prime 变量不会在调用中成为 'shared'，它只会每次创建一个新的 prime。

编辑：没有意识到您希望函数只打印出质数（如果它是质数），相应地更改了代码。

Answer 2

因为我们的目标是打印数字以防它是质数，所以让我们先做那部分。您的代码中已经有一个条件，但没有打印：

if a >= N:
    print(N)
    return

接下来我们需要处理所有N > 1:

的情况

if N == 2: 
    prime = True
    print(N)
    return 
elif (N % a) == 0:
    prime = False
    return is_prime(a+1,N)
else:
    prime = True
    print(N)

首先检查，if N == 2 是不必要的，因为之前已经有一个块处理所有 N 是质数的情况，因此可以将其删除。那就是说放在那里不会造成任何伤害。

检查 N 是否可被 a 整除的下一个块应该终止递归。既然你知道 N 不是质数，你应该就此打住。

当 N 不能被 a 整除时执行的最终块应该执行递归。按照现在的情况，递归一旦 N % a != 0 就停止，这显然是错误的。

这是一个经过上述修改和清理的工作示例：

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

Answer 3

您的函数有时 returns something 有时 returns nothing -- 它应该是一个或另一个，而不是两者。在这种情况下 is_prime() 看起来像一个布尔函数，所以它应该 return True 或 False。我们将打印留给调用者：

def is_prime(N, a=3):

    if N == 2:  # special case
        prime = True
    elif N <= 1 or N % 2 == 0:  # too small or even
        prime = False
    elif a * a > N:  # tried all divisors to sqrt, must be prime
        prime = True
    elif (N % a) == 0:  # divides evenly, not a prime
        prime = False
    else:  # can't tell yet, recursively try the next (odd) divisor
        prime = is_prime(N, a+2)

    return prime

for x in range(100):
    if is_prime(x):
        print(x)

保持简单。仔细考虑每一种可能的情况。避免不必要地增加缩进深度，这会使您的代码更加复杂。

上述解决方案试图通过避免偶数（除数和数字）并将除数限制为数字的平方根来加快素数检测。这可能很重要，因为如果没有这些优化，递归解决方案可能会运行在 N=1,000 左右超出调用堆栈 space 而上面的解决方案应该在不扩展调用堆栈的情况下达到 N=1,000,000。

Answer 4

def prime(n,j):
    if(n<2):
        return False
    if(j==n):
        return True
    if(n%j==0):
        return False
    return prime(n,j+1)

print(prime(n,2))

如果一个数只能被它自己和1整除，那么它就是质数。所以从 2 迭代到 n-1，如果 n 可以被 (2,3,4,..n-1) 中的任何一个整除 return False.
如果 j == n 那么 (2,3,4...n-1) 中没有可以被 n 整除的数，因此它是质数。

Answer 5

打印给定范围内的素数列表

l=[]
def primenum(x,y):
    global l
    if x==y:
        print(l)
    else:
        m=0
        for i in range(1,x+1):   
            if x%i==0:
                m+=1
        if m==2 or x==1:
            l+=[x,]
            return primenum(x+1,y)
        else:
            primenum(x+1,y)

Answer 6

def is_prime(n):
  def prime_helper(n, x):
    if n == 1:
      return False
    elif n % x == 0:
      return False
    else:
      return prime_helper(n , x+1) if x * x <= n else True 
  return prime_helper(n, 2)

如果您不想使用辅助函数

def is_prime(n, x=2):
    if n == 1:
      return False
    elif n % x == 0:
      return False
    else:
      return is_prime(n , x+1) if x * x <= n else True

此外，您不需要检查 (1 - N) 之间的所有数字，只需检查 sqrt(n) 以内的数字。您可以将迭代方法更改为

for 循环

from math import sqrt 
def is_prime(n):
  if n == 1:
     return False
  for i in range(2, round(sqrt(n)) + 1):
     if n % i == 0:
        return False
  return True

while 循环

def is_prime(n):
  if n == 1:
    return False
  i = 2
  while i * i <= n:
     if n % i == 0:
        return False
     i += 1
  return True

如何在 Python 中使用递归找到质数

How do I find a prime number using recursion in Python

python

recursion

primes

python-3.x

for 循环

while 循环