Ten thousand and first prime checker takes a very long time

Question

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

Answer 1

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 2

Your code does not work. Your main() has an infinite loop.

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.

Answer 3

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

Answer 4

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.

Answer 5

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)
        {
            testForPrime = testForPrime.add(BigInteger.valueOf(2));
            if(((primesProduct.gcd(testForPrime)).compareTo(BigInteger.ONE))==0)
            {
                primesProduct = primesProduct.multiply(testForPrime);
                primesFound = primesFound.add(BigInteger.ONE);
            }
        }
        System.out.println(new Date());
        System.out.println("found: "+testForPrime);
    }
}