我想知道这个程序如何知道一个数字是否是质数。我知道它会检查余数以找到要除以的偶数,但它如何知道一个数字只有 2 个因数?我对递归的概念很陌生,因此对步骤的解释会很有帮助,谢谢。
代码
def RecIsPrime(m):
"""Uses recursion to check if m is prime."""
def PrimeHelper(m, j):
"""Helper Function to iterate through all j less than m up to 1 to look for even divisors."""
if j == 1: # Assume 1 is a prime number even though it's debatable.
return True
else:
#do this task if both conditionals are true
#else break and return false.
return m % j != 0 and PrimeHelper(m, j - 1)
return PrimeHelper(m, m -1)
来源
https://github.com/hydrogeologist/LearningPython/blob/master/_recursion%20example%20in%20Python
行数:184 到 194
最佳答案
它检查是否有从 m - 1 到 1 的任何数字可以整除 m,它不仅仅检查偶数。
EG,对于RecIsPrime(10)
,您将调用以下嵌套函数:
PrimeHelper(10, 9) = 10 % 9 != 0 and PrimeHelper(10, 8)
↪ PrimeHelper(10, 8) = 10 % 8 != 0 and PrimeHelper(10, 7)
↪ PrimeHelper(10, 7) = 10 % 7 != 0 and PrimeHelper(10, 6)
↪ PrimeHelper(10, 6) = 10 % 6 != 0 and PrimeHelper(10, 5)
↪ PrimeHelper(10, 5) = 10 % 5 != 0 == false
10 % 5 != 0
为 false
,因此不会评估 and
的右侧。 PrimeHelper(10, 5)
将返回 false
并且不会继续递归。
在 PrimeHelper(10, 6)
中,您得到 10 % 6 != 0
为 true
,但我们刚刚看到了 PrimeHelper (10, 5)
为 false
因此这也将返回 false,所有其他调用也将返回 false。
关于python - 素数递归 - 它是如何工作的? (Python),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40438824/