java - JAVA中质数的递归方法

Question

首先，我知道这是一个简单的问题，而且我是初学者，所以请耐心等待。我在 Java 中的这项练习中遇到了问题，我正在练习测试，这确实破坏了我的自信心。所以无论如何，问题看起来像这样

 // Returns true if (and only if) n is a prime number;  n > 1 is assumed.
private static boolean isPrime(long n) {
    return isPrime(n, 2);
    // See the method isPrime below.
}

// Helper method for isPrime ...
private static boolean isPrime(long n, long m) {
    return (m * n > (m /* TODO: modify expression if necessary */))
            || (n % m == (0 /* TODO: modify expression if necessary */)
                && isPrime((m /* TODO: modify expression if necessary */), n + 1));
}

所以你应该将这些表达式填充到 TODO 所在的括号内。我的问题是我无法追踪它的作用。

isPrime((.....),n+1); 

如果有人可以就如何开始解决这个问题提供一些建议，我将非常感激。

Answer 1

这个问题不适合递归解决。或者至少不是一个高效的递归解决方案。

素数的定义是，如果 N 不能被除自身或 1 之外的任何正整数整除，则 N 是素数。使用递归处理该问题的正常方法是定义一个递归“is_divisible”函数:

# for integers m >= 1
is_prime(m):
    return is_divisible(m, 1)

is_divisible(m, n):
    if n >= m: return true
    if n == 1: return is_divisible(m, n + 1)
    if m % n == 0: return false  // HERE
    return is_divisible(m, n + 1)

OR(更高效的 3 参数版本)

# for all integers m
is_prime(m):
    if m == 1: return false
    if m >= 2: return is_divisible(m, sqrt(m), 2)
    error "m is not a positive integer"

is_divisible(m, max, n) :
    if n >= max: return true
    if m % n == 0: return false  // HERE
    return is_divisible(m, max, n + 1)

(在文献中，他们经常将诸如 is_divisible 之类的函数称为“辅助”函数。这是函数式编程中的常见工具。)

如果您尝试“优化”它，仅在这里考虑素数，您最终将得到双重递归......和指数复杂性。

<小时/>

这在 Java 中是非常“不自然”的，并且效率非常低(即使与使用循环的朴素素性测试相比¹)，因为 Java 不进行递归的尾部调用优化。事实上，对于足够大的N，您将得到一个StackOverflowError。

<小时/>

^{1 - 更好但仍然简单的方法是埃拉索尼斯筛法。有比这更好的素性测试，尽管它们相当复杂，并且在某些情况下是概率性的。}