CODEWITHSUNDEEP
java
Rakim
Rakim

Reputation: 1107

Recursively finding all prime numbers up to a given number (Project Euler 10) gives StackOverflow Error

I am trying to implement a recursive algorithm to find all the prime number up to the given number to solve Project Euler problem 10.

Whenever I try this for large numbers I get a StackOverflowError: null.

My code is:

public long sumOfPrimes(long num,  long start){
    if(start>num)
        return 0;
    else{
        boolean isPrime = true;
        for(long i=2; i<start; i++){
            if(start%i==0)
                isPrime = false;
        }
        if(isPrime && start>=2)
            return start+sumOfPrimes(num, start+1);
        else
            return sumOfPrimes(num, start+1);
    }
}

Upvotes: 0

Views: 686

Answers (1)

ljgw
ljgw

Reputation: 2771

You recurse for every number between start and num. When the difference is too great, you recurse too often and you get the StackOverflowError.

Try recursing only when you actually get to a prime to improve your results. (i.e. loop through the numbers between start and num until isPrime = true.

Upvotes: 2

Related Questions