java - Java递归中的堆栈溢出错误

Question

我正在尝试实现一个代码，该代码返回 200 万以下所有素数的总和。我有一个 isPrime(int x) 方法，如果数字是质数，它会返回 true。在这里:

public static boolean isPrime(int x) {

        for (int i = 2; i < x; i++) {

            if (x % i == 0) {
                return false;
            }

        }
        return true;

    }

我尝试递归实现的另一种方法只能工作到一定数量，超过该数量我会收到堆栈溢出错误。我让代码运行的最高值是 10,000。

这里是:

public static int sumOfPrimes(int a) {

    if (a < 2000000) {  //this is the limit

        if (isPrime(a)) {
            return a + sumOfPrimes(a + 1);

        } else {
            return sumOfPrimes(a + 1);
        }

    }
    return -1;
}

那么为什么当数字变大时会出现堆栈溢出错误，我该如何处理呢？ 另外，您通常如何处理为如此大的数字编写代码？ IE:像这样的正常数字操作，但对于更大的数字？我递归地写了这个，因为我认为它会更有效率，但它仍然无法工作。

Answer 1

你的isPrime函数效率很低，它不必去x，去x的平方根就够了。

但这不是您的解决方案不起作用的原因。递归深度不能达到 100 万。

我会使用 sieve of eratosthenes 迭代地解决这个问题并循环遍历生成的 boolean 数组。