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

Answer 3

You should save all the prime numbers you got so far into a look up list therefore you'll be checking if the number is divided by the numbers from that list. If not it's a prime number - go add it to the list.
Another idea is to replace number++; with number += 2; and start checking from 3 as soon as even numbers with exception for 2 are not prime.

Answer 4

I recently solved this problem. I'd suggest generating your primes with a Sieve of Eratosthenes, say all primes < 1 million. It's not a hard algorithm to implement, and it's fairly fast for the number of primes you need.

Answer 5

Compilers for some languages (e.g. many functional and semi-functional languages like Lisp) will convert tail recursion like you've used into iteration, but (apparently) the Java compiler isn't doing that for you. As a result, every recursive call is using stack space, and eventually you run out and the stack overflows.

Of course, for most purposes, you want to use a different algorithm -- what you're using right now is pretty awful as these things go. At the very least, you only need to check odd numbers up to the square root of the number you're testing...

Answer 6

Your strategy to test a prime is to check its divisibility with every smaller natural number.

If you shift your strategy to test for divisibility with just every smaller prime, you would save a whole lot of computation.

Answer 7

import java.util.*;

public class LargestPrime {
    public static boolean isPrime(long s) {
        for(long i = 2; i < s; i++) {
            if((s % i) == 0) return false;                   
        }
        return true;
    }

    public static void main(String[] args) {
        LargestPrime p = new LargestPrime();
        LinkedList<Long> arr = new LinkedList<Long>();
        for(long j = 2; j <= 999999; j++) {

            if(isPrime(j)) arr.add(j);

        }
        // System.out.println("List of Prime Number are: "+ arr);
        long t = arr.get(10001);

        System.out.println("The Prime Number At 10001st position: " + t);
    }
}

Answer 8

To solve this in general, you're going to have to switch from a recursive solution to an iterative one. (Every recursive algorithm can be expressed iteratively, too.)

Since function Prime is recursive, there will always be a system limit on how many times it can call itself.

However, you may have enough memory on your system to reach 10001. Java allows you to set the maximum amount of memory (stack, heap, etc) that the VM uses. Increase the stack memory number, and you'll probably be able to make it. See this page

http://docs.sun.com/source/817-2180-10/pt_chap5.html

for some of the Java VM options.

Answer 9

You could always use the Rabin-Miller primality test. It's a very easy to implement algorithm and very fast, though understanding how it works is a bit tougher.

Answer 10

package problems;

public class P_7 {
    /**
     * @param args
     */
    public static boolean prime(double num)
    {
        double x=2;
        double limit=(int) ((num/2)-(num/2)%1);
        while(x<=limit)
        {
            if(num%x==0)
                return false;
            x++;
        }
        return true;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i=1;
        int j=3;
        while(i<=10000)
        {
            if(prime(j))
            {
                System.out.println(i);
                i++;
                System.out.println(j);
            }
            j++;
        }
    }
}

this is my working answer.

Answer 11

In C... You can do shorter version, but whatever :D ..

#include <stdio.h>
#include <stdlib.h>

prost_br(int p)
{
    int br=0;

    for(int i=2;i*i<=p;i++)
    if(p%i==0)
    br++;

    if(br==0)
    return 1;
    return 0;
}

int main()
{
    long i=1;
    int br=0;
FILE *a;

a=fopen("10001_prst_numbers.txt","w");
if(a==NULL){printf("\nError!\a\n"); exit(1);}

    while(br!=10001)
    {
        i++;
        if(prost_br(i))
        {
            br++;
            fprintf(a,"%d ",i);
        }

    }
    char s[]={"10001th prime number is: "};
fprintf(a,"\n%s %d",s,i);
fprintf(stdout,"\n10001th prime number is: %d\n\a",i);

fclose(a);
system("Pause");
}

Answer 12

The problem lies in the recursively defined Prime(X,Y) function, but also in the algorithm used. There is only so much recursion depth that the function call mechanism of Java can accommodate before the call stack is exhausted, causing the "stack overflow" error.

It is enough to test for divisibility against all numbers below the square root of the number being tested. In terms of the OP code, that means starting not from Prime(N,N-1), but rather from Prime( N, floor( sqrt( N+1)) ). This change alone could be enough to prevent the SO error for this specific task, as the recursion depth will change from 10000 to just 100.

Algorithmic problems only start there. The Prime(X,Y) code counts down, thus testing the number by bigger numbers first. But smaller factors are found far more often; the counting should be done from the smallest possible factor, 2 (which is encountered for 50% of numbers), up to the sqrt of the candidate number. The function should be re-written as a simple while loop at this opportunity, too.

Next easy and obvious improvement is to ignore the even numbers altogether. 2 is known to be prime; all other evens are not. That means starting the loop from numberOfPrimes = 1; number = 3; and counting up by number += 2 to enumerate odd numbers only, having isPrime(N) test their divisibility only by the odd numbers as well, in a while loop starting with X = 3, testing for N % X and counting up by X += 2.

Or in pseudocode (actually, Haskell) , the original code is

main = print ([n | n<-[2..], isPrime(n)] !! 10000)  where   
  isPrime(n) = _Prime(n-1)  where
      _Prime(y) = y==1 || (rem n y > 0 && _Prime(y-1)) 
  -- 100:0.50s 200:2.57s 300:6.80s 10000:(projected:8.5h)
  --       n^2.4       n^2.4

the proposed fix:

main = print ((2:[n | n<-[3,5..], isOddPrime(n)]) !! 10000)  where   
  isOddPrime(n) = _Prime(3)  where
         _Prime(y) = (y*y) > n || (rem n y > 0 && _Prime(y+2)) 
  -- 100:0.02s 200:0.03s 300:0.04s 5000:3.02s 10000:8.60s
  --                                       n^1.5

Timings shown are for non-compiled code in GHCi (on a slow laptop). Empirical local orders of growth taken as log(t2/t1) / log(n2/n1). Even faster is testing by primes, and not by odd numbers.

btw, the original code prints not the 10001st prime, but the number above it.

Answer 13

public class progs {

public int nthPrime(int nth) {
    int ctr = 0;
    int num = 0;
    int x = 2;
    int infinite = 15;          // initial value good for 6 prime values
    while(x < infinite) {
        boolean isPrime = true; 
        for(int i = 2; i <= x / 2; i++) {
            if(x % i == 0) {
                isPrime = false;
            }
        }
        if(isPrime) {
            System.out.println(x);  // optional
            ctr++;
            if(ctr == nth) {
                num = x;
                break;
            }
        }
        x++;
        if(x == infinite) {     // for bigger nth requested prime value
            infinite++;     
        }
    }
    return num;
}

public static void main(String[] args) {
    int ans = new progs().nthPrime(10001);
    System.out.println("nth prime number is " + ans);
}

}