https://charlesreid1.com/w/index.php?action=history&feed=atom&title=Project_Euler%2F50 2026-06-18T23:14:15Z Revision history for this page on the wiki MediaWiki 1.39.12 https://charlesreid1.com/w/index.php?title=Project_Euler/50&diff=30597&oldid=prev 2026-06-16T14:34:52Z

<p>Automated edit (via create-page on MediaWiki MCP Server)</p> <p><b>New page</b></p><div><br /> ==Problem Statement==<br /> <br /> The prime 41 can be written as the sum of six consecutive primes:<br /> <br /> &lt;math&gt;41 = 2 + 3 + 5 + 7 + 11 + 13&lt;/math&gt;<br /> <br /> This is the longest sum of consecutive primes that adds to a prime below one-hundred.<br /> <br /> The longest sum of consecutive primes below one-thousand that adds to a prime contains 21 terms and is equal to 953.<br /> <br /> Which prime, below one-million, can be written as the sum of the most consecutive primes?<br /> <br /> ==Approach==<br /> <br /> ===Sieve of Eratosthenes===<br /> <br /> 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 &lt;code&gt;isPrime&lt;/code&gt; array provides O(1) primality testing for all integers in range.<br /> <br /> ===Collect Primes into a List===<br /> <br /> Iterate through the &lt;code&gt;isPrime&lt;/code&gt; array, collecting every prime into a compact &lt;code&gt;int[]&lt;/code&gt; array. This allows efficient iteration over only the primes (roughly 78,000 of them below one million), rather than scanning all one million numbers.<br /> <br /> ===Prefix Sum Array===<br /> <br /> Build a prefix sum (cumulative sum) array over the list of primes: &lt;code&gt;prefixSum[k]&lt;/code&gt; stores the sum of the first &lt;code&gt;k&lt;/code&gt; primes. With this structure, the sum of primes from index &lt;code&gt;i&lt;/code&gt; to &lt;code&gt;j-1&lt;/code&gt; is computed in O(1) time as &lt;code&gt;prefixSum[j] - prefixSum[i]&lt;/code&gt;. This avoids repeatedly summing ranges inside the nested loop.<br /> <br /> ===Sliding Window Search===<br /> <br /> The algorithm uses two nested loops:<br /> <br /> * &#039;&#039;&#039;Outer loop (i):&#039;&#039;&#039; the starting index of the consecutive prime sequence.<br /> * &#039;&#039;&#039;Inner loop (j):&#039;&#039;&#039; the ending index, initialized to &lt;code&gt;i + maxLen + 1&lt;/code&gt; so that only windows strictly longer than the current best are examined. This pruning avoids wasting time on sequences that cannot beat the record.<br /> <br /> 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 &lt;code&gt;isPrime&lt;/code&gt; array in O(1)), update &lt;code&gt;maxLen&lt;/code&gt; and record the prime.<br /> <br /> ===Return the Result===<br /> <br /> After all windows are examined, return the prime that was the sum of the most consecutive primes.<br /> <br /> ==Solution==<br /> <br /> Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem050.java<br /> <br /> ==Flags==<br /> <br /> {{ProjectEulerFlag}}</div>

Admin