Project Euler/50

Problem Statement

The prime 41 can be written as the sum of six consecutive primes:

$ 41 = 2 + 3 + 5 + 7 + 11 + 13 $

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime contains 21 terms and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Approach

Sieve of Eratosthenes

Generate all primes below 1,000,000 using a standard boolean sieve. All numbers from 2 to 999,999 are initially marked as prime, then multiples of each discovered prime are struck off. The resulting isPrime array provides O(1) primality testing for all integers in range.

Collect Primes into a List

Iterate through the isPrime array, collecting every prime into a compact int[] array. This allows efficient iteration over only the primes (roughly 78,000 of them below one million), rather than scanning all one million numbers.

Prefix Sum Array

Build a prefix sum (cumulative sum) array over the list of primes: prefixSum[k] stores the sum of the first k primes. With this structure, the sum of primes from index i to j-1 is computed in O(1) time as prefixSum[j] - prefixSum[i]. This avoids repeatedly summing ranges inside the nested loop.

Sliding Window Search

The algorithm uses two nested loops:

• Outer loop (i): the starting index of the consecutive prime sequence.
• Inner loop (j): the ending index, initialized to i + maxLen + 1 so that only windows strictly longer than the current best are examined. This pruning avoids wasting time on sequences that cannot beat the record.

For each window, compute the sum via the prefix array. If the sum exceeds the one-million limit, break the inner loop (since adding more primes would only increase the sum). If the sum is prime (checked via the isPrime array in O(1)), update maxLen and record the prime.

Return the Result

After all windows are examined, return the prime that was the sum of the most consecutive primes.

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem050.java