Project Euler task 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² + 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² 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.

Considering quadratics of the form:

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.

------------------------------------------------------------------------------

#include

#include

using namespace std;

const int iMin = -999;

const int iMax = 1000;

enum

{

UNKNOWN =0,

PRIME,

USUAL

} primeNumbers[1000000];

bool isPrime(int _iNum) {

if (_iNum <= 1)

return false;

if (primeNumbers[_iNum]) {

if (primeNumbers[_iNum] == PRIME)

return true;

return false;

} else {

for (int i = 2; i <= (int) sqrt((float)_iNum); i++)

if (_iNum % i == 0) {

primeNumbers[_iNum] = USUAL;

return false;

}

primeNumbers[_iNum] = PRIME;

return true;

}

}

int main() {

int iMaxN = 0;

int iCurA = 0, iCurB = 0;

for (int a = iMin; a < iMax; a++)

for (int b = 2; b < iMax; b++)

for (int n = 0; isPrime(n * n + a * n + b); n++)

if (n > iMaxN) {

iMaxN = n;

iCurA = a;

iCurB = b;

}

cout << "a: " << iCurA << endl;

cout << "b: " << iCurB << endl;

return 0;

}