**Problem 27:**

Euler published the remarkable quadratic formula:

*n*² + *n* + 41

It turns out that the formula will produce 40 primes for the consecutive values *n* = 0 to 39. However, when *n* = 40, 40^{2} + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when *n* = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula *n*² – 79*n* + 1601 was discovered, which produces 80 primes for the consecutive values *n* = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n² +an+b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value ofn

e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, *a* and *b*, for the quadratic expression that produces the maximum number of primes for consecutive values of *n*, starting with *n* = 0.

**Idea:**

I saw no simple way of doing this other than brute force. The number of calculations could be reduced by selecting *b* to be a prime number (whether positive or negative), but I figured that was too much work when it was much easier (with only slight performance hit) to just try all the numbers and count the number of consecutive primes, taking note of the coefficients when I found a pair that yielded a greater number of consecutive primes.

int answer = -1; int numberOfPrimes = 0; int answerA = 0; int answerB = 0; for(int a = -999; a < 1000; a++) { for(int b = -999; b < 1000; b++) { boolean consecutive = true; int n = 0; while(consecutive) { int value = (n*n) + a*n + b; if(BigInteger.valueOf(value).isProbablePrime(5)) { n++; } else { if(n > numberOfPrimes) { numberOfPrimes = n; answerA = a; answerB = b; } consecutive = !consecutive; } } } } answer = answerA*answerB; System.out.println("Answer: "+answer+" (a = "+answerA+", b = "+answerB+", primes = "+numberOfPrimes);