Project Euler Problem 50 Solution

Project Euler Problem 50 Solution

Consecutive Prime Sum

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 50 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?

Python Source Code

import Euler
p = Euler.prime_sieve(5_500_000)

for _ in range(int(input())):
    N = int(input())
    a, b, psum, pseqlen, mx = 0, 0, 0, 0, 0
    while a < len(p):
        while b < len(p) and psum + p[b] <= N:
            psum+= p[b]
            b+= 1
        while b - a > pseqlen and not Euler.is_prime(psum):
            psum-= p[b-1]
            b-= 1
        if b - a > pseqlen: pseqlen, mx = b-a, psum
        psum-= p[a]
        a+= 1
    print(mx, pseqlen)

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 50

HackerRank Project Euler 50: Which prime, $\le N$, can be written as the sum of the most consecutive primes?

Solution

Below is a brief explanation of how this solution solves the HackerRank version of Project Euler Problem 50, which asks for the prime below a given number $N$ that can be written as the longest sum of consecutive primes.

The Sliding Window Approach

For each query with input $N$, the objective is to find the prime (at most $N$) that can be expressed as the sum of the most consecutive primes. To achieve this, the code uses two pointers (a and b) and a running sum (psum). This technique is often referred to as a "sliding window." Initially, a and b both start at 0. The inner while loop expands the window to the right (increasing b) as long as adding the next prime does not exceed $N$. Whenever the sum of the primes in the window is itself prime, the var checks whether this window is the longest found so far. If it is, it updates the current best length (pseqlength) and the best prime (mx).

Contracting the Window and Producing the Result

Once the sum can no longer be extended without exceeding $N$, the code contracts the window from the left by subtracting p[a] from psum and moving a one step to the right. This enables checking other potential windows of consecutive primes. The loop continues until the left pointer a reaches the end of the prime list. At the end of each query, it prints out the prime mx (which represents the largest prime sum found under $N$) and its length pseqlength. This gives the required result for each input $N$.

Last Word