## Project Euler Problem #27

### February 14, 2010

Read the details of the problem here

Summary

Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Solution

I used a straightforward approach to this problem. I assumed that b had to be positive and that both |a| and |b| had to be prime numbers themselves to reduce the chance of b being a multiple of a so I used a sieve to generate the numbers and worked from that.

```def isPrime = new boolean[12000]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..<(int)Math.sqrt(isPrime.size())) {
if (!isPrime[i]) continue
def j = i + i
while (j < isPrime.size()) {
isPrime[j] = false
j += i
}
}

def ( answer, maxlen ) = [ 0, 0 ]

for (a in -999..<1000) {
if (!isPrime[Math.abs(a)]) continue
for (b in 1..<1000) {
if (!isPrime[b]) continue
def n = 0
while (isPrime[ (n * n) + (a * n) + b ]) {
n++
}
if (n > maxlen)
(maxlen, answer) = [ n, a * b ]
}
}
```

This runs in 0.76 seconds with the creation of the sieve taking 0.54 seconds (68%). Rather than generating lists of primes and working from that I just used the array directly as performance is generally better like that (though in this case it probably wouldn’t have mattered). Selection of the upper bound of the prime sieve was initially larger than the 12,000 shown in order to prevent out-of-bound exceptions.

Conclusion

I didn’t really use any specific Groovy feature here apart from multiple assignment in a few places and in the for-loop syntax. Performance was completely adequate for the scope of this problem.