如何在 Python 中使用递归找到质数 [英] How do I find a prime number using recursion in Python

问题描述

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

I have to find out whether number(N) is a prime or not using recursion, no loops are allowed. I've tried converting the usual code that uses a for loop to a recursive one, but it's not behaving the same. This function is included in another function, which is part of another function. only parameters a and N should be used and passed Here is my function.

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)

这是我尝试转换的代码.

Here is the code I tried to convert.

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")

推荐答案

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

Your solution is close, with just a few changes needed to make it work.

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 的情况下调用，因为任何其他值都没有意义.所以如果你像这样运行上面的函数，你应该得到正确的输出:

You didn't give any examples of calling this function, but I assume it's always called with a being 2, since any other value wouldn't make sense. So if you run the above function like so, you should get the right output:

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

我认为您对递归的工作方式有误解，您在函数体中分配了这个 prime 变量，但从未对它做任何事情.也许您的困惑来自对 Python 中作用域的误解.prime 变量不会在调用之间共享"，它每次只会创建一个新的 prime.

I think you have a misunderstanding of how recursion works, you're assigning this prime variable in the body of the function, but never doing anything with it. Maybe your confusion comes from a misunderstanding of scopes in Python. That prime variable will not be 'shared' across invocations, it will just create a new prime every time.

没有意识到您希望函数只打印素数，如果它是素数，相应地更改了代码.

Didn't realize you wanted the function to just print out the prime if it's a prime, changed the code accordingly.

这篇关于如何在 Python 中使用递归找到质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！