patternjavaMinor
Ten thousand and first prime checker takes a very long time
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.
The solution only took a couple of minutes and I didn't expect it to be as slow as it is...
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.