Finding the 10001st Prime Number

I’m working on Project Euler #7 and I coded :

public class Seven {

    public static void main(String[] args) {

        int i = 0;
        int c = 1;

        while (c <= 10001) {

            if (squareRootIsPrime(i)) {
                c++;
            }

            i++;

        }

        System.out.println(Math.sqrt(i));
    }

    public static boolean squareRootIsPrime (int n) {

        int x = 0;

        for (int d = 1; d <= n; d++) {
            if (n % d == 0) {x += 1;}
        }

        if (x == 3) {
            return true;
        } else {
            return false;
        }

    }

}

because square root of a number that has 3 factors is prime.
My code looks correct so far, but eclipse won’t print anything and terminate the program, so what’s wrong with my code?

The square of the 10001st prime is just under 11 billion. The largest value an int can hold is just over 2 billion. So the variable i will overflow long before it reaches the square of the 10001st prime. Because that happens, you’ll never get to see the 10001st prime.

In theory, this would work if you changed the type of the variable i and the parameter n to long. BUT if you do this, you’ll be left with code that has to evaluate about 60 quintillion % operations (that is, a 6 with 19 zeroes). Unless you’ve got an incredibly fast computer, this isn’t going to finish running in your life time.

You may want to think about what other algorithms you could use.

First of all, you should move the i++; line above the if (squareRootIsPrime(i)) – otherwise you’ll print the square root of the number following the result you actually search for.

The reason you don’t get the result printed is simply that the computer takes too long to calculate it. I am testing c <= 500 right now and it still hasn’t come to a result. Also, as Dawood already mentioned, int has a certain maximum number that we can’t overshoot.

Thinking about the algorithm, there’s a lot of tweaks you can do, however – for example does every prime number have a square you can check. Incrementing potential prime numbers instead of squares automatically excludes numbers that aren’t whole numbers as prime number candidates.

Here is a faster and optimized version of the algorithm.

public class Seven {

    public static void main(String[] args) {

        int i = 1;
        int c = 1;

        while (c <= 10001) {

            i++;

            if (isPrime(i)) {
                c++;
            }

        }

        System.out.println(i);
    }

    public static boolean isPrime(int i) {

        long n = (long)i*i;

        for (int d = 2; d < i; d++)
            if (n % d == 0) return false;
        return true;
    }
}

You have to set i = 1 first, since i gets incremented directly afterwards (prime numbers start at 2)

d doesn’t have to start at 1. A number is always dividable by that. That also means the number needs one factor less. But there’s more!

You can stop d right before i instead of n. The reason for this is that for every number bigger than i, we’d need a counterpart factor that’s smaller than i to multiply that number with if we want to get the result n. If we increment from 2 upwards to i, we tried all these counterpart numbers already, though, therefore it’s not needed to check any numbers bigger than i. Another factor less, since the number won’t be divided by itself anymore.

You also don’t need to check n / i, since i was the number to use as the method parameter in the first place, therefore it’s always going to be true – also, the root is the last one of the three factors of a square of a prime number.

We are left with 0 factors and can now safely state that if (n % d == 0), the parameter is not a prime number.

the 10001st prime is just 104743.

You can change your code to this:

public class Seven {
public static void main(String[] args) {
    int i = 0;
    int c = 1;
    while (c <= 10001) {
    if (IsPrime(i)) {
            c++;
            System.out.println(i);
        }
        i++;
    }
    System.out.println(i);
}
public static boolean IsPrime(long x) {
    if (x<2) return false;
    if (x<=3) return true;
    for (long j = 2; j <= Math.sqrt(x) + 1; ++ j) 
    if (x % j == 0) return false;
    return true;
}

}

The algorithm you judge the number is a prime is very slow. You can search that how to judge a number is prime. The fast time cost is O(sqrt(N)). And you should notice that if an j cause x mod j ==0 the loop will exit immediately. So this algorithm is much faster than you think.