java - Java计算第10001个素数时栈溢出

Question

我正在做欧拉计划的第 7 题。我应该做的是计算第 10,001^st 个素数。 (质数是大于 1 且只能被其自身和 1 整除的整数。)

这是我当前的程序:

public class Problem7 {
    public static void main(String args[]) {
        long numberOfPrimes = 0;
        long number = 2;
    
        while (numberOfPrimes < 10001) {
            if (isPrime(number)) {
                numberOfPrimes++;
            }
            number++;
        }
        System.out.println("10001st prime: " + number);
    }

    public static boolean isPrime(long N) {
        if (N <= 1)
            return false;
        else
            return prime(N, N - 1);
    }

    public static boolean prime(long X, long Y) {
        if (Y == 1)
            return true;
        else if (X % Y == 0)
            return false;
        else
            return prime(X, Y - 1);
    }
}

查找第 100 个^th 质数时效果很好，但运行非常大的输入(例如 10,001)会导致堆栈溢出。我该如何解决？

Answer 1

我认为问题在于您递归调用 Prime 以确定数字是否为素数。因此，要确定数字 1000 是否为素数，您需要递归调用 Prime 1000 次。每个递归调用都需要将数据保存在堆栈中。栈只有这么大，所以最终你会用完栈上的空间来继续进行递归调用。尝试使用迭代解决方案而不是递归解决方案。