## 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.