Stack overflow when calculating the 10,001st prime number in Java

Question

I am doing problem 7 of Project Euler. What I am supposed to do is calculate the 10,001^st prime number. (A prime number is an integer greater than one that is only divisible by itself and one.)

Here is my current program:

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);
    }
}

It works okay with finding, say the 100^th prime number, but running with very large inputs (such as 10,001) results in stack overflow. Why, and how can I fix this?

Answer 1

I think the problem is that you're recursively calling Prime to determine if a number is prime or not. So, to determine whether the number 1000 is prime or not, you're calling Prime 1000 times recursively. Each recursive call requires data to be kept on the stack. The stack is only so large, so eventually you run out of room on the stack to keep making recursive calls. Try using an iterative solution instead of a recursive solution.

Answer 2

Use "Sieve of Eratosthenes"

Java source:

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);
    }
}