如何在 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")

原文由 Amiel Moodley 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 变量不会在调用之间“共享”，它只会创建一个新的 prime 每次。

编辑：没有意识到你想要函数只打印出素数，如果它是素数，相应地改变了代码。

原文由 Marcus Buffett 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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) 中的任何一个整除，则返回 False。

如果 j == n 则 (2,3,4…n-1) 中没有可被 n 整除的数字，因此它是质数。

原文由 Parvez Ahamad Shaik 发布，翻译遵循 CC BY-SA 4.0 许可协议