Ten thousand and first prime checker takes a very long time

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

• Re. how to make it faster, that's probably been explained in answers to some of the other questions about prime numbers. Mar 23 '14 at 1:28
• Use solutions to previously solved problems to solve new problems. Suppose you want to know if 12347 is prime. If you have already computed the prime numbers less than or equal to root 12347, then you only need to check whether 12347 is divisible by each of them, not all the numbers up to the root. Mar 23 '14 at 6:49
• Skipping every other number is smart. You could be smarter by starting i at 12, increasing by 6 each time, and then checking i-1 and i-5 for primeness in the loop. Clearly i, i-2, i-3 and i-4 are divisible by either 2 or 3. Mar 23 '14 at 6:56
• "I didn't expect it to be as slow as it is" -- The infinite loop identified in 200_success' answer and Jamal's comment explains why it's slower than slow (i.e. endless). Mar 23 '14 at 8:54
• I've noticed that you use i += 2;, probably because you've eliminated all multiples of 2 from the possible prime numbers. Why only for 2? Why not take that to its logical conclusion, and eliminate all multiples of every prime number you find? That's what the Sieve of Eratosthenes does - you should look into that if you want a faster prime number generator. Mar 23 '14 at 8:57

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;
}
• Answer to this question suggest your answer is correct: that the repeated sqrt isn't optimized away by the JVM. Mar 23 '14 at 1:34

Trial division is a simple way to test whether a single number is prime. However, to test many numbers, you want to use the Sieve of Eratosthenes.

You isPrime() reports that 1 is prime and 2 is not. That might be acceptable if you take care to never call it with those parameters and document those special cases in JavaDoc.

• 1. I don't see the infinite loop in main? 2. The Sieve of Eratosthenes would work well here, but there's the question of knowing in advance how large to make your table of candidates. Also it would require O(n) memory instead of O(1) as for trial division. 3. That's a good point about isPrime, but you'll notice that in fact it is only ever called with num >= 3. Mar 23 '14 at 3:32
• @NateEldredge: count is only incremented if isPrime() returns true. Once the while loop gets a non-prime number (4 being the first one), the if will be skipped, so count will not increment.
– Jamal
Mar 23 '14 at 4:31
• @Jamal Actually, i will get stuck at 9. Mar 23 '14 at 4:45
• @NateEldredge 2. The n th prime is approximately n ln n; it turns out that for 10000, this estimate is about 12% too low, but still it's a useful guide. In my opinion, using 100 kB for the sieve is a worthwhile expense. 3. Avoiding the erroneous cases of isPrime() is fine, but my point is that failure to document those cases is poor practice. Mar 23 '14 at 5:08
• Nate, at the point where you have so many primes that the memory matters, you would use consecutive sieves, for example make a sieve for the primes from 1 to 1 million, another for primes from 1 million to 2 millions, and so on, to keep memory use under control. Mar 23 '14 at 13:09

I think you need <= in isPrime's for loop: because otherwise you'll decide that 25 is prime.

• Moreover, you probably want to replace floor with ceil; due to the limited precision of floating point, Math.sqrt(25) could return 4.99999996 or something similar. Mar 23 '14 at 1:57
• @NateEldredge This document says, "the result is the double value closest to the true mathematical square root of the argument value" ... so perhaps the result is exact (an integer value) if the argument is a perfect square. Mar 23 '14 at 2:04
• Ok, true, assuming that your floating point implementation is able to represent small integers exactly (which most are). Mar 23 '14 at 3:26

Unless your compiler is quite clever, it will calculate Math.floor (Math.sqrt (num)) on every single iteration of the loop, which will probably take three times longer than the rest of the operations.

"i < Math.floor (Math.sqrt (num))" is really, really bad. It makes your code think that squares of primes are prime (for example 9, 25, 49), but also products of consecutive twin primes, like 15 = 3x5, 35 = 5x7, 143 = 11x13 and so on.

As mentioned, the loop in main stops making progress when it reaches the first non-prime. I would write the loop in the most straightforward way:

for (int i = 3; ; i += 2)
{
if (isPrime (i))
{
// Whatever you want to do with primes
}
}

And in general, I wouldn't put lots of code into main (). main () should in my opinion process any parameters, then call code doing the work.

In your code, the i+=2 should be outside the if statement, otherwise it gets stuck on the first non prime number:

i += 2;
if(isPrime(i)) {
count++;
}

Moving the sqrt calculation outside is one option, another one is to test for the square value like this because a multiplication is not as expensive as the square root calculation:

for(int i = 3; i*i < num ; i+=2)

For testing why it is slow start with printing out the result of every while iteration, so you can if it just gets slower with larger numbers or if it gets stuck somewhere.

You could also try to work with BigInteger and another algorithm, this one takes around 5 seconds on my old PC and it should work fine with larger numbers too.

import java.math.BigInteger;
import java.util.Date;

public class Euler7
{
public static void main(String[] args)
{
System.out.println(new Date());
BigInteger primesProduct = BigInteger.valueOf(2*3);
BigInteger primesFound = BigInteger.valueOf(2);
BigInteger testForPrime = BigInteger.valueOf(3);
BigInteger limit = BigInteger.valueOf(10001);
while(primesFound.compareTo(limit)<0)
{