3770. Largest Prime from Consecutive Prime Sum

MediumArrayMathNumber Theory

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

Your task is to find a special kind of prime number that satisfies two conditions at the same time:

It must be the sum of one or more consecutive prime numbers starting from 2. This means we add up primes in order beginning with 2. For example, the possible sums are:
- 2 (just the first prime)
- 2 + 3 = 5 (the first two primes)
- 2 + 3 + 5 = 10 (the first three primes)
- 2 + 3 + 5 + 7 = 17 (the first four primes)
- and so on.
The sum itself must also be a prime number. Looking at the sums above, 2 is prime, 5 is prime, 10 is not prime, 17 is prime, and so on. So only sums that turn out to be prime are valid candidates.

Among all such valid numbers that are less than or equal to n, you must return the largest one.

If there is no such number that is less than or equal to n, return 0.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Number Theory?

This problem maps to Number Theory through a short path in the full flowchart.

Generating primes via sieve and checking which cumulative prime sums are themselves prime is a pure number theory problem.

Open in Flowchart

Intuition

The key observation is that the valid numbers we are looking for do not depend on n itself. The set of "prime sums of consecutive primes starting from 2" is fixed — it is always the same list regardless of what n we are given.

This naturally suggests a preprocessing idea: instead of recomputing everything for each query, we can build the complete list of valid numbers once, and then answer any query quickly.

To build this list, we walk through the following steps:

First, we need all prime numbers up to some upper limit. Since the problem guarantees n is bounded, we can pick a safe maximum (here 5 × 10^5) and use the Sieve of Eratosthenes to find every prime up to that bound efficiently.
Next, we add the primes one by one in order (2, then 2 + 3, then 2 + 3 + 5, ...), keeping a running total t. Each time we extend the sum, we check whether the current running total t is itself a prime number. If it is, we record it into a list s.

Because we always add primes in increasing order, the list s of valid numbers is naturally sorted in ascending order. This sorted property is what makes answering queries fast.

For a given n, we want the largest valid number that does not exceed n. Since s is sorted, we don't need to scan through it linearly — we can use binary search to instantly locate the rightmost value that is ≤ n. If such a value exists, it is our answer; otherwise we return 0.

In short: the answers come from a small fixed sorted list, so we precompute it once and use binary search to handle each query in logarithmic time.

Pattern Learn more about Math patterns.

Solution Approach

We use the pattern Preprocessing + Binary Search.

Step 1: Sieve of Eratosthenes

First, we determine all prime numbers up to an upper bound mx = 500000. We create a boolean array is_prime where is_prime[i] tells us whether i is prime:

mx = 500000
is_prime = [True] * (mx + 1)
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, mx + 1):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, mx + 1, i):
            is_prime[j] = False

For every number i starting from 2, if it is still marked prime, we add it to the primes list and then mark all of its multiples (starting from i * i) as non-prime. After this loop, primes holds every prime up to mx, and is_prime lets us check primality in O(1).

Step 2: Build the list of valid prime sums

We accumulate consecutive primes starting from 2, keeping a running total t. The array s begins with [0] to act as a sentinel, so that queries with no valid answer naturally return 0:

s = [0]
t = 0
for x in primes:
    t += x
    if t > mx:
        break
    if is_prime[t]:
        s.append(t)

Each time we extend the sum, we check whether the running total t is itself prime using the precomputed is_prime array. If it is, we append it to s. We stop early once t exceeds mx, since any further sum would be out of range. Because primes are added in increasing order, s ends up sorted in ascending order.

Step 3: Answer each query with binary search

Since s is sorted, finding the largest value ≤ n becomes a binary search problem:

class Solution:
    def largestPrime(self, n: int) -> int:
        i = bisect_right(s, n) - 1
        return s[i]

bisect_right(s, n) returns the insertion point just past all elements ≤ n. Subtracting 1 gives us the index of the largest valid value not exceeding n. If no valid prime sum is ≤ n, the index lands on the sentinel 0, which correctly returns 0.

Complexity

Preprocessing time: The sieve runs in O(mx · log log mx), and building s runs in O(mx). This is done only once.
Per query time: O(log m), where m is the size of s (which is very small).
Space: O(mx) for the sieve arrays.

This approach is efficient because the expensive work is shared across all queries, leaving only a fast logarithmic lookup for each individual call.

Example Walkthrough

Let's trace through the solution with a small example where n = 20.

Step 1: Generate primes (Sieve of Eratosthenes)

For our small example, we only need the primes up to 20:

primes = [2, 3, 5, 7, 11, 13, 17, 19]

The is_prime array lets us check any value instantly. For instance:

is_prime[5] = True
is_prime[10] = False
is_prime[17] = True

Step 2: Build the list of valid prime sums

We start with the sentinel list s = [0] and a running total t = 0. Then we add primes one at a time, checking whether each running total is itself prime:

Prime added	Running total `t`	Is `t` prime?	Action	`s` after step
`2`	`2`	✅ Yes	append `2`	`[0, 2]`
`3`	`5`	✅ Yes	append `5`	`[0, 2, 5]`
`5`	`10`	❌ No	skip	`[0, 2, 5]`
`7`	`17`	✅ Yes	append `17`	`[0, 2, 5, 17]`
`11`	`28`	❌ No	skip	`[0, 2, 5, 17]`

At this point, the next sum 28 already exceeds our n = 20, but in the full solution we keep going until t > mx. For this walkthrough, the valid candidates ≤ 20 are:

s = [0, 2, 5, 17, ...]

Notice that s is naturally sorted because primes are always added in increasing order.

Step 3: Answer the query with binary search

Now we want the largest value in s that is ≤ 20.

i = bisect_right(s, 20) - 1

bisect_right(s, 20) finds the insertion point just past all elements ≤ 20. Looking at s = [0, 2, 5, 17, 28, ...], the values 0, 2, 5, 17 are all ≤ 20, but 28 is not. So the insertion point is 4.
Subtracting 1 gives index 3.
s[3] = 17.

Result: 17 ✅

This is correct because 17 = 2 + 3 + 5 + 7 (a sum of consecutive primes starting from 2), 17 is itself prime, and it is the largest such number not exceeding 20.

Edge case check: If we had n = 1, then bisect_right(s, 1) = 1, and s[1 - 1] = s[0] = 0. The sentinel 0 correctly signals that no valid prime sum exists ≤ 1.

Solution Implementation

1from bisect import bisect_right
2
3# Upper bound for the sieve
4MAX_LIMIT = 500000
5
6# Sieve of Eratosthenes: mark which numbers up to MAX_LIMIT are prime
7is_prime = [True] * (MAX_LIMIT + 1)
8is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime
9
10primes = []
11for num in range(2, MAX_LIMIT + 1):
12    if is_prime[num]:
13        primes.append(num)
14        # Mark all multiples of `num` (starting from num*num) as non-prime
15        for multiple in range(num * num, MAX_LIMIT + 1, num):
16            is_prime[multiple] = False
17
18# Build the list of "prime sums of consecutive primes":
19# accumulate primes one by one, and record the running sum
20# whenever that running sum is itself a prime within the limit.
21prime_sums = [0]  # sentinel value 0 so queries below n's smallest case work
22running_sum = 0
23for prime in primes:
24    running_sum += prime
25    if running_sum > MAX_LIMIT:  # beyond our sieve range, stop
26        break
27    if is_prime[running_sum]:
28        prime_sums.append(running_sum)
29
30
31class Solution:
32    def largestPrime(self, n: int) -> int:
33        # Find the rightmost prime-sum value that is <= n.
34        # bisect_right gives the insertion point after all values <= n,
35        # so subtracting 1 yields the index of the largest such value.
36        index = bisect_right(prime_sums, n) - 1
37        return prime_sums[index]
38

1class Solution {
2    // Upper bound for the sieve of Eratosthenes
3    private static final int MAX_VALUE = 500_000;
4
5    // isPrime[i] is true if i is a prime number
6    private static final boolean[] isPrime = new boolean[MAX_VALUE + 1];
7
8    // List of all prime numbers up to MAX_VALUE
9    private static final List<Integer> primes = new ArrayList<>();
10
11    // List of "prime sums": cumulative sums of consecutive primes
12    // that are themselves prime (with a leading 0 as sentinel)
13    private static final List<Integer> primeSums = new ArrayList<>();
14
15    static {
16        // Initialize the sieve: assume all numbers are prime initially
17        Arrays.fill(isPrime, true);
18        isPrime[0] = false; // 0 is not prime
19        isPrime[1] = false; // 1 is not prime
20
21        // Sieve of Eratosthenes to find all primes up to MAX_VALUE
22        for (int i = 2; i <= MAX_VALUE; i++) {
23            if (isPrime[i]) {
24                primes.add(i);
25                // Mark multiples of i as non-prime, starting from i * i
26                // Guard against integer overflow with a long comparison
27                if ((long) i * i <= MAX_VALUE) {
28                    for (int j = i * i; j <= MAX_VALUE; j += i) {
29                        isPrime[j] = false;
30                    }
31                }
32            }
33        }
34
35        // Build the list of prime cumulative sums.
36        // Sentinel 0 allows safe lookup of the "previous" element.
37        primeSums.add(0);
38        int runningSum = 0;
39        for (int prime : primes) {
40            runningSum += prime;
41            // Stop once the cumulative sum exceeds the sieve range
42            if (runningSum > MAX_VALUE) {
43                break;
44            }
45            // Keep the cumulative sum only if it is itself prime
46            if (isPrime[runningSum]) {
47                primeSums.add(runningSum);
48            }
49        }
50    }
51
52    public int largestPrime(int n) {
53        // Find the insertion point for (n + 1) in the sorted primeSums list.
54        // This effectively locates the first element strictly greater than n.
55        int index = Collections.binarySearch(primeSums, n + 1);
56        if (index < 0) {
57            // binarySearch returns (-(insertion point) - 1) when not found;
58            // convert it back to the insertion point
59            index = ~index;
60        }
61        // Return the largest prime sum that is <= n
62        return primeSums.get(index - 1);
63    }
64}
65

1// Upper bound for the sieve range.
2static const int kMaxValue = 500000;
3
4// is_prime[i] == true  ->  i is prime.
5static vector<bool> is_prime(kMaxValue + 1, true);
6
7// All primes in the range [2, kMaxValue].
8static vector<int> primes;
9
10// Prime-valued cumulative sums of consecutive primes
11// (with a leading 0 as a sentinel for binary search).
12static vector<int> prime_sums;
13
14// Static initializer: runs once before main() to precompute the tables.
15static auto init = [] {
16    is_prime[0] = false;
17    is_prime[1] = false;
18
19    // Sieve of Eratosthenes: collect every prime up to kMaxValue.
20    for (int i = 2; i <= kMaxValue; i++) {
21        if (is_prime[i]) {
22            primes.push_back(i);
23            // Start marking multiples from i*i; guard against overflow.
24            if (1LL * i * i <= kMaxValue) {
25                for (int j = i * i; j <= kMaxValue; j += i) {
26                    is_prime[j] = false;
27                }
28            }
29        }
30    }
31
32    // Sentinel value so that upper_bound always has a valid predecessor.
33    prime_sums.push_back(0);
34
35    // Accumulate primes; whenever the running sum is itself prime, record it.
36    int running_sum = 0;
37    for (int prime : primes) {
38        running_sum += prime;
39        if (running_sum > kMaxValue) break;  // Beyond the sieve's range.
40        if (is_prime[running_sum]) {
41            prime_sums.push_back(running_sum);
42        }
43    }
44
45    return 0;
46}();
47
48class Solution {
49public:
50    int largestPrime(int n) {
51        // Find the first prime-sum strictly greater than n,
52        // then step back one to get the largest value <= n.
53        auto it = upper_bound(prime_sums.begin(), prime_sums.end(), n);
54        return *(it - 1);
55    }
56};
57

1// Upper bound for the sieve and prefix-sum computation.
2const MAX_LIMIT = 500000;
3
4// isPrimeFlags[i] indicates whether i is a prime number.
5const isPrimeFlags: boolean[] = new Array<boolean>(MAX_LIMIT + 1).fill(true);
6isPrimeFlags[0] = false;
7isPrimeFlags[1] = false;
8
9// All prime numbers in the range [2, MAX_LIMIT].
10const primeList: number[] = [];
11
12// Prefix sums of primes that are themselves prime (including the leading 0).
13const primeSumList: number[] = [];
14
15/**
16 * Initialization performed once at module load:
17 *   1. Run the Sieve of Eratosthenes to find all primes up to MAX_LIMIT.
18 *   2. Build a running sum over the primes; whenever the running sum is
19 *      itself a prime (and within range), record it in primeSumList.
20 */
21(function init(): void {
22    // Sieve of Eratosthenes.
23    for (let i = 2; i <= MAX_LIMIT; i++) {
24        if (isPrimeFlags[i]) {
25            primeList.push(i);
26            // Only sieve when i * i stays within bounds to avoid overflow / waste.
27            if (i * i <= MAX_LIMIT) {
28                for (let j = i * i; j <= MAX_LIMIT; j += i) {
29                    isPrimeFlags[j] = false;
30                }
31            }
32        }
33    }
34
35    // Seed the prefix-sum list with 0 so largestPrime always has a valid floor.
36    primeSumList.push(0);
37
38    let runningSum = 0;
39    for (const prime of primeList) {
40        runningSum += prime;
41        // Stop once the running sum exceeds the precomputed prime table range.
42        if (runningSum > MAX_LIMIT) {
43            break;
44        }
45        // Keep the running sum only if it is itself a prime number.
46        if (isPrimeFlags[runningSum]) {
47            primeSumList.push(runningSum);
48        }
49    }
50})();
51
52/**
53 * Find the rightmost index in a sorted array whose value is strictly less
54 * than the given target. Equivalent to lodash's sortedIndex(arr, target) - 1.
55 *
56 * @param sortedArray - Array sorted in ascending order.
57 * @param target      - The value to compare against.
58 * @returns The index of the last element strictly less than target, or -1.
59 */
60function lowerBoundIndex(sortedArray: number[], target: number): number {
61    let low = 0;
62    let high = sortedArray.length; // Exclusive upper bound.
63
64    // Binary search for the first index where value >= target.
65    while (low < high) {
66        const mid = (low + high) >>> 1;
67        if (sortedArray[mid] < target) {
68            low = mid + 1;
69        } else {
70            high = mid;
71        }
72    }
73
74    // The element just before that position is the last value < target.
75    return low - 1;
76}
77
78/**
79 * Return the largest recorded prime-sum value that is less than or equal to n.
80 *
81 * @param n - The upper bound (inclusive) to search for.
82 * @returns The largest value in primeSumList that does not exceed n.
83 */
84function largestPrime(n: number): number {
85    // Searching for (n + 1) and stepping back gives the largest value <= n.
86    const index = lowerBoundIndex(primeSumList, n + 1);
87    return primeSumList[index];
88}
89

Time and Space Complexity

Time Complexity:

The preprocessing phase consists of two parts:

Sieve of Eratosthenes: Building the is_prime array up to mx (denoted as M) takes O(M log log M) time. This is the classic complexity of the sieve, derived from the harmonic series over primes M · Σ(1/p), which converges to O(M log log M).
Building the prefix-sum prime array s: Accumulating the sum of primes and checking primality (an O(1) lookup in is_prime) runs at most until the cumulative sum t exceeds M. This iterates over a subset of primes and takes O(M) time in the worst case, which is dominated by the sieve.

For each query, the largestPrime method uses bisect_right on array s, which performs a binary search in O(log k) time, where k is the length of s. In this problem, k ≤ 40, so each query is effectively O(1).

Therefore, the overall preprocessing time complexity is O(M log log M), and each query takes O(log k) time.

Space Complexity:

The is_prime array requires O(M) space.
The primes list stores all primes up to M, which contains O(M / log M) elements by the prime number theorem, i.e., O(M / log M) space.
The prefix-sum prime array s holds at most k elements, requiring O(k) space.

The dominant term is the is_prime array, so the overall space complexity is O(M).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Stopping the sum accumulation too early with `break` on a non-prime check

A frequent mistake is to confuse the two different stopping conditions when building prime_sums. The loop must continue accumulating consecutive primes even when the running sum is not prime — it only records the sum when it is prime, and only stops when the sum exceeds the limit.

A buggy version often looks like this:

for prime in primes:
    running_sum += prime
    if is_prime[running_sum]:
        prime_sums.append(running_sum)
    else:
        break          # WRONG: stops as soon as a sum is non-prime

The very first sum is 2 (prime), but the next sum 2 + 3 = 5 is prime, then 2 + 3 + 5 = 10 is not prime. With the buggy break, the loop would terminate at 10 and never discover later valid sums like 17, 41, 197, etc. This silently produces a far-too-short prime_sums list and wrong answers for larger n.

Solution: Keep accumulating regardless of whether the current sum is prime. Only break when the running sum exceeds the sieve's range, since beyond that point primality can no longer be checked and no value would be ≤ n anyway:

running_sum = 0
for prime in primes:
    running_sum += prime
    if running_sum > MAX_LIMIT:   # the ONLY valid early-exit condition
        break
    if is_prime[running_sum]:      # record, but never stop, on this branch
        prime_sums.append(running_sum)

Related pitfall: Indexing into the sieve with an out-of-range sum

If you check is_prime[running_sum] before verifying running_sum <= MAX_LIMIT, you risk an IndexError once the cumulative sum grows past MAX_LIMIT. Always perform the range check first, then the primality lookup — exactly the ordering shown above. This guarantees every index into is_prime is valid.

Pitfall: Forgetting the sentinel `0`

Omitting the leading 0 in prime_sums = [0] breaks the "return 0 when no answer exists" requirement. When n is smaller than the smallest valid sum (2), bisect_right(prime_sums, n) - 1 would yield index -1, which in Python wraps around to the last element instead of signaling "no result." The sentinel 0 ensures that index -1... actually lands on a meaningful fallback: with the sentinel present, the index 0 correctly returns 0, giving the intended behavior cleanly.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering