python - 素数递归 - 它是如何工作的？ (Python)

Question

我想知道这个程序如何知道一个数字是否是质数。我知道它会检查余数以找到要除以的偶数，但它如何知道一个数字只有 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

Answer 1

它检查是否有从 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。