HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Ten thousand and first prime checker takes a very long time

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
longtimetenthousandfirsttakesandprimecheckervery

Problem

I am attempting problem 7 on Project Euler. I have come up with this solution which works fine for finding smaller nth prime numbers, but really lags when it comes to higher nth prime numbers. I am not quite sure where to start to make it more efficient.

public class TenThousandFirstPrime {

    public static boolean isPrime(int num) {
        if(num % 2 == 0) return false;
        for(int i = 3; i < Math.floor(Math.sqrt(num)); i += 2) {
            if(num % i == 0) return false;
        }

        return true;
    }

    public static void main(String[] args) {
        int count = 2;  
        int i = 3;
        while(count <= 10001) {
            if(isPrime(i)) {
                i += 2;
                count++;
            }
        }
        System.out.println(i);
    }
}


The solution only took a couple of minutes and I didn't expect it to be as slow as it is...

Solution

The square root calculation could just be done before the loop. Since this value does not change within the function, it doesn't need to be recalculated each time through the loop.

public static boolean isPrime(int num) {
    if (num % 2 == 0) return false;

    int squareRoot = Math.floor(Math.sqrt(num));
    for (int i = 3; i < squareRoot; i += 2) {
        if (num % i == 0) return false;
    }

    return true;
}

Code Snippets

public static boolean isPrime(int num) {
    if (num % 2 == 0) return false;

    int squareRoot = Math.floor(Math.sqrt(num));
    for (int i = 3; i < squareRoot; i += 2) {
        if (num % i == 0) return false;
    }

    return true;
}

Context

StackExchange Code Review Q#45115, answer score: 6

Revisions (0)

No revisions yet.