Project Euler Problem #58

May 21, 2010

Read the details of the problem here

Summary

Investigate the number of primes that lie on the diagonals of the spiral grid.

Solution

Not a particularly difficult problem to understand, the only real issue was that the potential scope of the primes didn’t lend themselves to a sieve approach so I used BigInteger support for prime determination. There shouldn’t be that many numbers to check. It’s only necessary to check three corners of the square as the lower right will never be prime.

On this basis I coded up a fairly straightforward brute-force approach as shown below. There are some micro-optimisations that could be made to remove some repeated multiplications with additions, for example, the increase of sqr on each iteration, or the calculation of the cell value, but this is only going to save a couple of hundred milliseconds at best.

Integer.metaClass.isPrime() { ->
    delegate.toBigInteger().isProbablePrime(100)
}

def (answer, primes, count, side) = [ 0, 0, 1, 3 ]

while (answer == 0) {

    def sqr = side * side
    primes += (1..3).findAll { (sqr - it * (side-1)).isPrime() }.size()
    count += 4

    if (primes / count < 0.1) answer = side

    side += 2
}

Run time is 2.4 seconds, so not the fastest solution in the world. Using a non-sieving isPrime(int) method coded in native Java brings the runtime down to 0.38 seconds so it’s actually spending quite a lot of time in prime determination.

Conclusion

Again, not really a Groovy solution in that it didn’t use many of the clever Groovy features, though the ability to add the Integer.isPrime() was nice. I did try coding the isPrime method in Groovy but that pushed the time up above 8 seconds so still an acceptable result but not as good as the BigInteger approach and, as that’s part of the JVM runtime it’s a better solution in my opinion.

Advertisements

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: