## 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, 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.

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| < 1000where |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.

**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; cout<<"Answer: "<<(max_a * max_b)<<endl; return 0; }

max_a: -61

max_b: 971

max_count: 71

Answer: -59231

real 0m1.584s

user 0m1.528s

sys 0m0.062s