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万的递归深度.

我会迭代地解决这个问题,使用eratosthenes的筛子并在结果boolean阵列上循环.