Problem Analysis
This problem asks me to search a family of quadratic expressions of the form n^2 + an + b, with integer coefficients bounded by |a| < 1000 and |b| <= 1000. For each pair (a, b) I feed in consecutive non-negative integers n = 0, 1, 2, ... and count the longest unbroken run of prime numbers the formula produces before the first non-prime value. The answer is the product a * b for the pair with the longest run.
The single observation that makes this tractable is a boundary condition. At n = 0 the formula collapses to just b, so if b is not prime the run has length zero. Only prime values of b can ever begin a meaningful run. Since there are only 168 primes below 1000, this insight shrinks the candidate set for b from 2001 integers to roughly 168 magnitudes (each usable with either sign). The remaining work is a brute-force scan over the ~1000 values of a. Each primality test is done by trial division at O(sqrt(V)) cost per value. With P primes, A values of a, runs of length at most R (~80), and values up to V_max (~2 * 10^6), the overall cost is roughly O(P * A * R * sqrt(V_max)) - large in the abstract, but fast in practice because almost all runs collapse after a handful of steps.
Solution Approach
Sieve-constrained brute-force search
The Python and C files share index 0: they implement the same algorithm, with the C version being a direct translation that benefits from compiled arithmetic in the hot inner loop. I describe the algorithm once and note the language-specific differences as they arise.
Step 1 - Generate prime candidates for b. I generate all primes up to the limit (1000) using the Sieve of Sundaram. This sieve operates entirely on odd numbers: it marks every integer of the form i + j + 2ij (for positive integers i, j) as composite within an array of size (N-1)/2; each surviving index i corresponds to the odd prime 2i + 1, and the prime 2 is added explicitly. I chose Sundaram over the more familiar Sieve of Eratosthenes mainly for variety; at this problem size both have equivalent cost, and the Sundaram array is half the size since it skips even numbers.
Step 2 - Restrict the parity of a. For every odd prime b the code steps a in increments of 2 starting from 1; only b = 2 uses step 1 from 0. The reasoning is a parity argument. With odd b, consider n = 1: the value is 1 + a + b. For this to be prime (and not 2, which would force a very short run for these magnitudes) it must be odd, so a must be odd. Exploring only odd magnitudes of a therefore covers all coefficient pairs that can produce a long run while halving the iteration count - a cheap arithmetic filter applied before the expensive primality tests.
Step 3 - Enumerate sign combinations. Rather than looping a from -999 to 999 and b over both signs, I loop a from 0 upward and b over positive primes only, then evaluate all four signed pairs explicitly: (+a, +b), (+a, -b), (-a, -b), (-a, +b). Their products are +ab, -ab, +ab, -ab respectively, computed inline so no extra multiplication is needed. These four cover every distinct signed combination for a given pair of magnitudes.
Step 4 - Measure the prime run. The helper prime_run(a, b) increments x from 0 and tests whether |x^2 + ax + b| is prime, stopping at the first failure and returning the count. I take the absolute value before the test because negative integers are never prime, and a negative output simply ends the run - taking the magnitude lets me detect both signs uniformly. In C the value is held in a long long to avoid integer overflow, since the quadratic can reach roughly 2 * 10^6.
Step 5 - Track the best result. In Python I build a list of (run_length, product) tuples and call max(), which compares lexicographically: the longest run wins, and ties break on the larger product. The C version replicates this exactly with explicit comparisons (run > best_run, then products[c] > best_product on a tie).