27.cpp

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

namespace {

class PrimeCheck {
 public:
  PrimeCheck() :
      _current_limit(23),
      _known_primes({2, 3, 5, 7, 11, 13, 17}) { }

  bool is_prime(long n) {
    if (n < _current_limit) {
      return binary_search(_known_primes.begin(), _known_primes.end(), n);
    }

    for (long i = _current_limit; i < (n + 1); ++i) {
      bool is_prime = true;
      for (auto p = _known_primes.begin(); p != _known_primes.end(); ++p) {
        if (i % *p == 0) {
          is_prime = false;
          break;
        }
      }
      if (is_prime) {
        _known_primes.push_back(i);
      }
    }
    _current_limit = n;
    return _known_primes.back() == n;
  }

 private:
  long _current_limit;
  vector<long> _known_primes;
};

long sequence_length(PrimeCheck *check, long a, long b) {
  for (long n = 0; ; n++) {
    long value = n * n + a * n + b;
    if (value < 0 || !check->is_prime(value)) {
      return n;
    }
  }
}

pair<long, long> find_max() {
  PrimeCheck check;
  const long kLimit = 999;
  long max_count = 0, max_a = LONG_MAX, max_b = LONG_MAX;

  for (long a = -kLimit; a < (kLimit + 1); a++) {
    for (long b = -kLimit; b < (kLimit + 1); b++) {
      long this_count = sequence_length(&check, a, b);
      if (this_count > max_count) {
        max_a = a;
        max_b = b;
        max_count = this_count;
      }
    }
  }

  cout << "max_count = " << max_count << endl;
  return make_pair(max_a, max_b);
}

}

int main() {
  auto result = find_max();
  cout << result.first * result.second << endl;
}