在Java中计算第10,001个素数时堆栈溢出

Question

我正在做Euler项目的问题7.我应该做的是计算10,001 ^st素数.(素数是一个大于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 ^个素数,但运行非常大的输入(例如10,001)会导致堆栈溢出.为什么,我该如何解决这个问题？

Answer 1

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

Answer 2

使用" Eratosthenes的筛子 "

Java来源:

public class Main {
    public static void main(String args []){
        long numberOfPrimes = 0;
        int number = 1;
        int maxLimit = 10000000;
        boolean[] sieve = new boolean[maxLimit];
        for ( int i = 2; i < maxLimit; i++ ) {
            if ( sieve[i] == true ) continue;

            numberOfPrimes++;

            if ( numberOfPrimes == 10001 ) {
                number = i;
                break;
            }

            for ( int j = i+i; j < maxLimit; j += i )
                sieve[j] = true;
        }
        System.out.println("10001st prime: "+ number);
    }
}