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!

Advertisements

2 Responses to “Project Euler Problem #7”


  1. […] 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 […]

  2. Hans Says:

    Same comments as for your prime sieve for problem 10


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: