Euler discovered the remarkable quadratic formula:

n2+n+41n2+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤390≤n≤39. However, when n=40,402+40+41=40(40+1)+41n=40,402+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,412+41+41n=41,412+41+41 is clearly divisible by 41.

The incredible formula n2−79n+1601n2−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤790≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n2+an+bn2+an+b, where |a|<1000|a|<1000 and |b|≤1000|b|≤1000

where |n||n| is the modulus/absolute value of nn
e.g. |11|=11|11|=11 and |−4|=4|−4|=4

Find the product of the coefficients, aa and bb, for the quadratic expression that produces the maximum number of primes for consecutive values of nn, starting with n=0n=0.

package main

import (
      "fmt"
)

func IsPrime(n int) bool {
      if n < 2 {
              return false
      }

      for i := 2; i*i <= n; i++ {
              if n%i == 0 {
                      return false
              }
      }
      return true
}

func FindConsecutiveN(a, b int) int {
      isPrime := true
      n := 0
      for isPrime {
              result := n*n + a*n + b
              isPrime = IsPrime(result)
              if isPrime {
                      n++
              } else {
                      return n
              }
      }
      return -1
}

func main() {
      maxN := 0
      maxA := -11111
      maxB := -11111
      for a := -999; a < 1000; a++ {
              for b := -1000; b < 1001; b++ {
                      n := FindConsecutiveN(a, b)
                      if n == -1 {
                              panic("n cannot be -1")
                      }
                      if n > maxN {
                              maxN = n
                              maxA = a
                              maxB = b
                              fmt.Println("current max (a,b,n)", a, b, n)
                      }
              }
      }
      fmt.Println("max (a,b,n)", maxA, maxB, maxN)
}

current max (a,b,n) -999 2 1
current max (a,b,n) -996 997 2
current max (a,b,n) -499 997 3
current max (a,b,n) -325 977 4
current max (a,b,n) -245 977 5
current max (a,b,n) -197 983 6
current max (a,b,n) -163 983 7
current max (a,b,n) -131 941 8
current max (a,b,n) -121 947 9
current max (a,b,n) -105 967 11
current max (a,b,n) -61 971 71
max (a,b,n) -61 971 71