JAVA素数的递归方法

首先我知道这是一个简单的问题，我是初学者，所以请耐心等待。我一直有这个练习在Java中的问题，我正在练习测试，这真的搞砸了我的自信。所以反正这个问题是这样的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);

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

来源

2015-12-06 Rorie

一个数字只有在它只能被1整除时才是整数。它的补充说明是它不是素数，如果它被任何其他素数均匀分配（即模数返回0）。应该有助于思考这个问题。 –

是的我明白，问题是如果数字是素数，并且n％m == 0对于只有非素数的情况为真，则该方法应该返回true。所以如果n是一个将是假的素数，并且假&&真仍然是假的。 – Rorie

'isPrime（（m/* TODO：如果需要修改表达式* /），n + 1））'正在检查除数'm'的素数，而不是'n'。如果'm'不是素数，'n'不是素数。 –

此问题不适用于递归解决方案。或者至少不是高效的递归解决方案。

素性的定义是，N是素数，如果它不是由除了本身或1.正常的方式来处理，使用递归是定义一个递归“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 “辅助” 功能的功能，这是在功能的编程的常用工具。）

如果您试图“优化”，只考虑HERE的素数，则最终会出现双递归和指数复杂性。

这是Java都非常“不自然”，并将于效率极其低下的（即使使用循环天真素性测试相比），因为Java没有做递归的尾部调用优化。事实上，对于足够大的N，您将获得StackOverflowError。

^{1 - 一个更好的，但还是简单的办法是Erathones的筛。对于素数的测试比它有更好的测试，虽然它们相当复杂，而且在某些情况下是概率性的。}

来源

2015-12-06 03:35:55

我们可以只用两个参数来做到这一点吗？只需使用m/2而不是max？如果n> = m/2：返回true 如果n == 1：返回is_divisible（m，n + 1） if m％n == 0：return false //如果n> = m/2则返回true 这里 return is_divisible（m，n + 1）' - 这样的事情？ – Rorie

是的。查看我的更新。 –

是的，这很有道理，非常感谢！ – Rorie

JAVA素数的递归方法

回答

相关问题