Problem Analysis
I am asked to find the prime below one million that can be written as the sum of the most consecutive primes. The naive reading of this problem invites an O(n^3) catastrophe: for every starting prime, try every length, and for every candidate length re-add a run of primes and test the total for primality. The two ideas that collapse this into something fast are a prefix sum array and monotonicity-based pruning. A prefix sum array S stores running totals, so that S[k] is the sum of the first k primes; the sum of any contiguous block from index j to i-1 is then just S[i] - S[j], computed in constant time. Without it, every candidate sum is a fresh O(n) scan.
Two observations prune the search. First, because all primes are positive, the prefix sums are strictly increasing - so as I shrink j, the candidate sum S[i] - S[j] grows monotonically, and once it crosses the limit, every longer run from the same endpoint also crosses it and I can stop immediately. Second, I only care about runs longer than the best found so far, so I start the inner loop at j = i - best_length - 1 and never even look at runs that cannot improve the answer. Primality of each candidate is settled in O(1) by a Boolean sieve - an array indexed by value where the entry is true exactly when that value is prime. Building the sieve costs O(n log log n); the doubly-nested loop, thanks to the two prunes, runs in near-linear time in practice. The dominant cost is therefore the sieve itself.
Solution Approach
Prefix-Sum Sieve Search (Python and C)
Both p0050_s0.py and p0050_s0.c implement the same four-step algorithm; they differ only in idiom and arithmetic width.
Step 1 - Generate primes. I generate all primes up to max_limit with the Sieve of Sundaram. Sundaram works on odd numbers only: it marks every value of the form i + j + 2*i*j as composite, then maps each surviving index i to the odd prime 2*i + 1, prepending the prime 2. I chose it largely for variety - the more familiar Sieve of Eratosthenes is in the same complexity class and would serve equally well. The output is a dense ascending array of primes.
Step 2 - Build the prefix-sum array. I build prime_sums with prime_sums[0] = 0 and prime_sums[k] equal to the sum of the first k primes. That leading zero is a sentinel: it lets a run starting at the very first prime be written as prime_sums[i] - prime_sums[0], in exactly the same form as every other run, so the inner loop needs no special case.
Step 3 - Build a fast primality lookup. In Python I make a set from the prime tuple, giving O(1) average membership tests. In C I calloc a byte array of size max_limit + 1 and set is_prime[p] = 1 for each prime - O(1) worst-case lookup with excellent cache behaviour.
Step 4 - Double-loop search with pruning. The outer loop advances the right endpoint index i. The inner loop starts at j = i - best_length - 1 rather than i - 1, so any larger j - which would yield a run no longer than the current best - is skipped outright. As j decrements, the candidate prime_sums[i] - prime_sums[j] grows; the moment it exceeds max_limit I break. When a candidate is prime, I record the new best length and best value. The C version additionally guards j_start < 0 with a continue and checks possible_prime >= 2 before indexing the sieve.
Language differences. Python uses itertools.accumulate to build the prefix sums in one compiled call, and relies on arbitrary-precision integers so overflow is impossible. The C version builds the prefix sums in a manual loop and stores them as long long (64-bit), because the sum of all primes below one million is roughly 37 billion - far past the 32-bit signed limit of about 2.1 billion. That difference in arithmetic, plus Python's dynamic dispatch, explains why the C version is roughly 60 times faster on the main case (0.0026 s versus 0.1615 s).