JAVA中质数的递归方法 [英] Recursive method for prime numbers in JAVA

问题描述

首先，我知道这是一个简单的问题，我是初学者，因此请耐心等待. 我在使用Java进行此练习时遇到了问题，并且正在练习进行测试，而这真的使我的自信心一团糟. 所以无论如何问题都是这样

First of all I know this is kind of a simple question and I am a beginner so please bear with me . I have been having problems with this exercise in Java and I'm practising for a test and this one really messed up my self-confidence. So anyways the problem looks like this

 // 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所在的括号内. 我的问题是我无法跟踪它的作用.

So you're supposed to fill these expressions inside of the brackets where TODO is . My problem is that I just can't trace what this does.

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

如果有人能就如何开始解决此问题提供一些建议，我将非常感激.

If someone could just offer some advice on how to start solving this problem I would be very grateful .

推荐答案

此问题不适用于递归解决方案.或至少不是 efficiency 递归解决方案.

This problem is not amenable to recursive solution. Or at least not an efficient recursive solution.

素数的定义是，如果N不能被除其本身或1以外的任何正整数整除，则N是素数.使用递归来处理该素的正常方法是定义一个递归的"is_divisible"函数:

The definition of primality is that N is prime if it is not divisible by any positive integer other than itself or 1. The normal way to handle that using recursion would be to define a recursive "is_divisible" function:

# 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参数版本)

OR (more efficient 3 parameter version)

# 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之类的函数称为辅助"函数.这是函数式编程中的常用工具.)

(In the literature, they often call functions like is_divisible "auxiliary" functions. This is a common tool in functional programming.)

如果尝试优化"以仅考虑HERE上的质数，则最终将导致两次递归..和指数复杂性.

If you try to "optimize" that to only consider prime numbers at HERE, you will end up with double recursion .. and exponential complexity.

这在Java中都是非常不自然的"，并且效率极低(甚至与使用loop ¹ 进行的朴素素性测试相比)也是如此，因为Java不会对递归进行尾调用优化.实际上，对于足够大的N，您将获得一个StackOverflowError.

This is all very "unnatural" in Java, and will be horribly inefficient (even compared with a naive primality test using a loop¹) because Java doesn't do tail-call optimization of recursion. Indeed, for large enough N you will get a StackOverflowError.

^{1-一种更好但仍然简单的方法是Erathones筛网.相对于原始性，有更好的测试方法，尽管它们相当复杂，并且在某些情况下是概率性的.}

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