## 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) { answer = i 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!

January 7, 2010 at 01:09

[…] I’ve changed my sieve creation look from being a Java-like for (;;) construct that I’ve used before to a verbose while() loop. I found that the former was taking upwards of 7 seconds to run i.e. a […]

July 26, 2010 at 11:09

Same comments as for your prime sieve for problem 10