[C/C++] Project Euler #27 Quadratic Primes

In the given quadratic formula \(n^2 + an + b\), n is an integer starting from 0, and a and b are integers satisfying the range |a| < 1000 and |b| < 1000. The goal is to find the values of a and b that produce the longest sequence of primes for consecutive values of n, and calculate the product \(a \times b\).

Summary:
1. Find a and b such that the quadratic formula \(n^2 + an + b\) produces the maximum number of consecutive primes for n.
2. Compute the product of these a and b.

---

The quadratic formula \(n^2 + n + 41\) is a well-known example of a prime-generating quadratic. It produces 40 consecutive primes for n values from 0 to 39.

To generate even more primes, larger values may be needed. Looking at the problem’s conditions, let’s analyze the formula further:

\[ n^2 + an + b \quad \text{where} \quad |a| < 1000 \quad \text{and} \quad |b| < 1000 \]

We can simplify the problem by focusing on specific cases:
• When n = 0, the formula becomes b. For the formula to produce primes, b must itself be a prime number.  If b is not prime, then no values of a can satisfy the condition.
• If b is prime, then a must satisfy certain properties. Specifically, a must be greater than -b, and it must be an odd number. If |a| is even, the formula will produce even (and therefore non-prime) values for odd n.  Thus, |a| must be odd.

Rather than checking primality for each generated number, we can precompute a list of primes within a sufficiently large range to reduce the computational cost.  While dynamic programming could also be used, this solution uses a precomputed set of primes to optimize prime-checking.

 

generating prime numbers

The source code is provided for reference only.

//------------------------------------------------
//    Project Euler #27 - Quadratic Primes
//        - by Aubrey Choi
//        - created at 2015-10-15
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

void getprimes(unsigned char primes[], int limit);

int main()
{
    unsigned char primes[20000/8];

    memset(primes, 0, sizeof(primes));
    getprimes(primes, 20000);

    int max = 0;
    int maxa, maxb;

    for( int b = 3 ; b < 1000 ; b += 2 )
    {
        if( !(primes[b/8] & (1<<(b%8))) ) continue;

        for( int a = -b ; a < 1000 ; a += 2 )
        {
            int n;
            for( n = 1 ; ; n++ )
            {
                int c = n*n + a*n + b;
                if( c <= 0 ) break;
                if( !(primes[c/8] & (1<<(c%8))) ) break;
            }
            if( max < n )
            {
                max = n;
                maxa = a;
                maxb = b;
            }
        }
    }
    printf("Ans = %d(a = %d, b = %d, max = %d)\n", maxa*maxb, maxa, maxb, max);
}

void getprimes(unsigned char primes[], int limit)
{
    primes[0] = 4;
    for( int i = 3 ; i < limit ; i += 2 )
    {
        int j;
        for( j = 3 ; j*j <= i && (i%j) ; j+=2 ) ;
        if( j*j > i ) primes[i/8] |= 1<<(i%8);
    }
    return;
}