Archive

Posts Tagged ‘Quadratic primes’

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.

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.

 

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

Advertisements