Trying to calculate the 10001st prime number in Java.

Question

Greetings. I am doing Problem 7 from Project Euler. What I am supposed to do is calculate the 10001st prime number. (A prime number being a number 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 100th prime number, but when I enter very large numbers such as 10001 it causes a stack overflow. Does anyone know of a way to fix this? Thanks for reading my problem!

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

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

I'm not a Java programmer, but I recently wrote a prime calculator in C# that seems to be pretty fast (fast enough for me, at least). It will get all primes between 0 and 1,000,000 in under 300 milliseconds on my machine (which is almost 80K primes).

    List<int> primes = new List<int>();
    primes.Add(2);

    for (int i = 3; i < 1000000; i += 2)
    {
        bool isPrime = true;
        int stoppingPoint = (int)Math.Pow(i, 0.5) + 1;
        foreach (int p in primes)
        {
            if (i % p == 0)
            {
                isPrime = false;
                break;
            }

            if (p > stoppingPoint)
                break;
        }

        if (isPrime)
        {
            primes.Add(i);
        }
    }

It should be fairly straightforward to translate that to Java, right?

The logic is to only use primes as divisors when testing and never test with anything greater than the square root of the tested value because anything beyond that is redundant.

Answer 7

Recursion may not be the best approach, but you can enlarge the heap: java -Xms1024M -Xmx1024M Problem7. See java - the Java application launcher.

Addendum: @meriton raises a compelling point about memory allocation, which will probably change as the questioner's code evolves. The -Xss option is also available.

Answer 8

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 9

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 10

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.