## Project Euler Problem #7

### January 6, 2010

Read the details of the problem here

Summary

Find the 10001st prime.

Solution

I took a brute force approach to this and used a simple prime sieve with a fairly arbitrary but generous upper limit and then just counted through the primes in the sieve.

```def isPrime = new boolean[200000]
Arrays.fill(isPrime, true);
isPrime[1] = false

for (int i in 2..isPrime.size()**0.5) {
if (isPrime[i]) {
for (j = i + i; j < isPrime.size(); j += i) isPrime[j] = false
}
}

def (answer, n) = [ 0, 0 ]
for (i in 2..<isPrime.size()) {
if (isPrime[i]) {
n++
if (n == 10001) {
break
}
}
}```

This completed in 1.3 seconds with the generation of the sieve taking 1.2 seconds, although with some judicious tweaking of the upper bound, once the answer was known, the runtime comes down to 0.99 seconds. I could further reduce the runtime during the count itself by only checking odd numbers but it’s not going to make that much difference to the overall duration.

Conclusion

Groovy didn’t really offer much in the way of assistance in this solution. The code in pretty much plain Java and runs MUCH slower that an equivalent 100% Java solution. Such an implementation, even with the broader upper bound, completes within 9 ms – that’s around 0.7% of the runtime. Groovy is 140x slower than Java in this particular scenario!

I strongly suspect that, at some point, I’m going to have to build (or source) some sort of prime engine in Java for use in the Groovy solutions if I’m going to be keeping within the 15 seconds of allotted time.

Even using the BigInteger#isProbablePrime method is quite slow, with a simple counting solution based on this taking 8.14 seconds in Groovy and 7.72 seconds in Java. Interestingly, making the prime check only on odd numbers brings the Groovy runtime down to 7.89 seconds – a saving of just 3%. The isProbablePrime method must (obviously) be efficient at ruling out even numbers!