## Project euler 27: Quadratic primes

Euler discovered 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, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² − 79n + 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.

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

where |n| is the modulus/absolute value of n
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.

Solution:

It is self explanatory.

```#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 100000
vector <long> prime(0);

bool * seive_helper(bool primes[], int range)
{
for (int i = 3; i <= range / 2 ; ++i, ++i) {
for(int j =  i * 3; j <= range ; j += (i << 1)) {
primes[j] = true;
}
}
}

void  seive(int range)
{
int count = 0;
bool primes[MAX] = {false};
for(int i = 4; i <= range; ++i, ++i) {
primes[i] = true;
}
seive_helper(primes, range);
for(int i = 2; i <= range; ++i) {
if (!primes[i]) {
prime.push_back(i);
}
}
}

bool isPrime(long num, int range)
{
int i = 0;
while (i <= range) {
if (num == prime[i])
return true;
else if (num < prime[i])
return false;
i++;
}
return false;

}

int main()
{
long long sum = 0;
int max_count = 0;
int max_a;
int max_b;
seive(10000);
for (int i = -1000; i <= 1000; i++) {
for(int j = -1000; j <= 1000; j++) {
int n = 0;
int count = 0;
while(isPrime(n * n + i * n + j, 10000)) {
count++; n++;
}
if (count > max_count) {
max_count = count;
max_a = i;
max_b = j;
}
}
}
cout<<"max_a: "<<max_a<<endl;
cout<<"max_b: "<<max_b<<endl;
cout<<"max_count: "<<max_count<<endl;

return 0;
}

```

max_a: -61
max_b: 971
max_count: 71

real 0m1.584s
user 0m1.528s
sys 0m0.062s