Stack overflow error in Java recursion

Question

I'm trying to implement a code that returns the sum of all prime numbers under 2 million. I have an isPrime(int x) method that returns true if the the number is prime. Here it is:

public static boolean isPrime(int x) {

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

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

        }
        return true;

    }

And the other method, which I'm trying to implement recursively, only works until a certain number, over that number and I get a stack overflow error. The highest I got the code to work was for 10,000.

Here it is:

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

So why do I get a stack overflow error when the number gets bigger and how can I deal with this? Also, how do you normally deal with writing code for such big numbers? IE: normal number operations like this but for larger numbers? I wrote this recursively because I thought it would be more efficient but it still wont work.

Answer 1

Your isPrime function is inefficient, it doesn't have to go to x, it's enough to go to the square root of x.

But that is not the reason why your solution doesn't work. You cannot have a recursion depth of 1 million.

I would solve this problem iteratively, using the sieve of eratosthenes and for loop over the resulting boolean array.