In this blog post we will be looking at problem 7 of Project Euler and we will program a solution in Java.

The problem of Project Euler found here, below is the problem for quick lookup.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

-Project Euler problem 7

What is a prime?

A prime number is a number only dividable by itself or one without a remainder.

If you take 3 for example you will see that 2 gives you a remainder(.5) but it is dividable by 3 and 1 without a remainder, so 3 is a prime number. If you consider 4 as a prime number you test it with 2 & 3, if you divide 4 by 2 you do not get a remainder you get the whole number 2, so 4 cannot be a prime number it is a composite number.

Do remember that 1 is not a prime number!

A function to figure out if a number is prime:

public static boolean isPrime(int number){
    boolean isPrime = true;
    if (number <= 1){
        isPrime = false;
    }else if (Math.sqrt(number) % 1 == 0) {
        isPrime = false;
    }else{
        double sqrt = Math.sqrt(number);
        for (int i = 2; i <= sqrt; ++i){
            if (number % i == 0){
                isPrime = false;
                break;
            }
        }
    }
    return isPrime;
}

We start by assuming the input number is a prime by setting the boolean ‘isPrime’ to true. After that we start the if else sequence with the first check. If the number is 1 or lower we set ‘isPrime’ to false since negative numbers and one are not primes and return false. If the first check fails we go to the second if where we check the square root of the number is a whole number, if it is the number is not a prime. To check if the square root is a whole number we use modulo 1. Which means if it is any sort of whole number it leaves 0, if it does the number is a composite number and we set prime to false and return that.

If both of the first if’s fail we go into the else where we start by getting the square root of the input number which we use as the max for the loop counter. We set the i variable(the loop counter) to 2 and increment it with 1 every loop. This loop gives us all whole numbers between one and the square root of the number. We keep checking in the if inside the for loop whether the input number modulo loop counter is 0. If it is this number is not a prime and we set ‘isPrime’ to false and break out of the for loop returning the false value. if we go to the entire loop ‘isPrime’ does not get set to false and we return true that the input number is a prime.

In the for loop we use square root as loop maximum since no number above the square root has to be considered.

The main program loop

int i = 0;
int primeCount = 0;
while (primeCount < 10001){
    if (isPrime(i)){
        primeCount += 1;
    }
    i += 1;
}

System.out.println(i - 1);

It’s a simple loop that goes from 0 up to 10000, in the loop we check if the ‘i’ variable is a prime. If it is we increment primeCount. Once we exit the loop we print the ‘i’ variable minus one since we increment i at the end of the loop even if the 10001 prime has been found.

With the 10001th prime being: 104743

Check out the ‘Project Euler in Java’ page for more solutions!

Link to github.

That was Project Euler problem 7 in Java!