java - 我在 Java 中遇到了一些递归问题

Question

任务是实现一个程序，计算给定数字sumtoBreak有多少个不同的素数和。

方法 primeSum 应该从数字 sumtoBreak 中减去所有可能的素数 currprime，直到 sumtoBreak 变为零并且然后为每种可能性返回(总和)一个。为了解释所有的可能性，在每个衰退步骤中，它都称自己为

1. 与 sumtoBreak - currprime 加上
2. 使用 nextPrime 调用自身。

我的问题是，除非 sumtoBreak 一开始就为零，否则 java 不会返回任何内容。
很高兴获得任何建议!

这是代码(我知道带有嵌套 if 语句的代码中的括号是多余的，但我只是想确保这不是问题):

这是固定代码:

public class PrimeSum {
    public static boolean isPrime(int primecandidate) {
        int count = 0;
        for (int i = 2; i <= primecandidate / 2; i++) {
            if (primecandidate % i == 0)
                count++;
        }
        if (count == 0)
            return true;
        else
            return false;
    }

    public static int nextPrime(int currprime) {
        int j = currprime + 1;
        while (!isPrime(j))
            j++;
        return j;
    }

    public static int primeSum(int sumtoBreak, int currprime) {
        if (sumtoBreak == 0) {
            return 1;
        } else {
            if (sumtoBreak < 0 || currprime > sumtoBreak) {
                return 0;
            } else {
                return primeSum(sumtoBreak, nextPrime(currprime)) + primeSum(sumtoBreak - currprime, currprime);
            }
        }

    }

    public static void main(String[] args) {
        System.out.println(primeSum(Integer.parseInt(args[0]), 2));
    }
}

Answer 1

这不会回答您的问题，但会更正 isPrime 方法中的错误并更快地更快计算结果:

private static boolean isPrime(final int primecandidate) {

    if ( primecandidate <  2) {        // 0 & 1 are NOT Prime
        return false;
    }
    if ((primecandidate & 0x1) == 0) { // Even is NOT Prime...
        return primecandidate  == 2;   // ...except for 2 (and 0).
    }
    for (int i = 2, iMax = (int) Math.sqrt(primecandidate); i <= iMax; i++) {
        if (primecandidate % i == 0) {
            return false;
        }
    }
    return true;
}

注意以下几点:

• 最后一个参数 primecandidate 被标记为最终参数
• 它将 0 和 1 的结果更正为 false
• 该方法被标记为私有(private)
• iMax 是 Sqrt(primecandidate) 而不是 primecandidate/2
• iMax 计算一次，而不是每次迭代
• 我使用一种我称之为“如果你完成了，就完成了”的策略。
  含义:不要设置标志(根据您的情况计算)，直接出去!

另请注意，有一个 apache commons Math3 函数...

org.apache.commons.math3.primes.Primes.isPrime(j)

对于较小的值 (<= Short.MAX_VALUE)，速度显着变慢
对于较大的值(约 Integer.MAX_VALUE)

稍微

还有一个 BigInteger.isProbablePrime(...) 函数，但我的基准测试表明它相当慢。

我希望这有一点帮助？