Project Euler Problem #58

May 21, 2010

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.

KeyZero Conversation