LeetCode Problem 3770

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

LeetCode 3770 - Largest Prime from Consecutive Prime Sum

Problem Understanding

The problem gives us an integer n and asks us to find the largest prime number that satisfies two conditions:

1. It is less than or equal to n.
2. It can be written as the sum of one or more consecutive prime numbers starting from 2.

The phrase "starting from 2" is very important. We are not allowed to choose an arbitrary sequence of consecutive primes. Every valid sum must begin with the first prime number, 2.

For example, the sequence of prime numbers begins as:

2, 3, 5, 7, 11, 13, 17, ...

The valid sums are therefore:

• 2
• 2 + 3 = 5
• 2 + 3 + 5 = 10
• 2 + 3 + 5 + 7 = 17
• 2 + 3 + 5 + 7 + 11 = 28
• and so on

Among these cumulative sums, we only care about those that are themselves prime numbers and do not exceed n.

The goal is to return the largest such prime. If no valid prime sum exists, we return 0.

The constraint is:

• 1 <= n <= 5 * 10^5

This upper bound is large enough that repeatedly testing primality with expensive methods or recomputing prime sequences many times would be inefficient. We need a solution that can efficiently generate primes and evaluate cumulative sums up to 500,000.

Some important edge cases are immediately visible:

• n = 1, no prime can be formed, so the answer is 0.
• n = 2, the sum 2 itself is valid and prime.
• Many cumulative prime sums are not prime. For example, 2 + 3 + 5 = 10, which should be ignored.
• The largest valid answer may occur much earlier than the largest cumulative sum below n.

Approaches

Brute Force Approach

A straightforward idea is to generate primes one by one, maintain the cumulative sum, and whenever a new sum is produced, test whether that sum is prime.

To do this naively, we could:

1. Generate primes using trial division.
2. Keep adding them to a running total.
3. For every cumulative sum not exceeding n, perform another primality test.
4. Track the largest prime cumulative sum.

This approach is correct because it explicitly examines every possible consecutive-prime sum beginning with 2.

However, it is inefficient. Generating primes via repeated trial division is expensive, and repeatedly performing primality checks introduces additional cost. As n approaches 500,000, this becomes unnecessarily slow.

Key Insight

The crucial observation is that every valid candidate is simply a prefix sum of the prime sequence.

If we generate all primes up to n using the Sieve of Eratosthenes, we immediately obtain:

• Fast prime generation.
• Constant-time primality lookup using the sieve array.

Then we can iterate through the primes in order, maintain a running prefix sum, and stop once the sum exceeds n.

Every prefix sum represents exactly one valid consecutive-prime sum starting from 2.

Whenever the current prefix sum is prime according to the sieve, it becomes a candidate answer.

Because the prefix sums are generated in increasing order, the last valid prime prefix sum encountered is automatically the largest answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n√n)	O(1)	Trial division for generating and checking primes
Optimal	O(n log log n)	O(n)	Sieve plus linear prefix-sum scan

Algorithm Walkthrough

1. Create a Sieve of Eratosthenes up to n. The sieve will allow us to determine whether any value from 0 to n is prime in constant time.
2. Extract all prime numbers from the sieve into a list. These primes are naturally ordered as 2, 3, 5, 7, ....
3. Initialize a running sum variable prefix_sum = 0.
4. Initialize the answer variable answer = 0.
5. Iterate through the prime list in ascending order.
6. Add the current prime to prefix_sum. At this point, prefix_sum represents the sum of consecutive primes starting from 2.
7. If prefix_sum > n, stop the loop. Since all future primes are positive, every later prefix sum will be even larger.
8. Check whether prefix_sum is prime by consulting the sieve.
9. If prefix_sum is prime, update answer = prefix_sum.
10. Continue until the loop terminates.
11. Return answer.

Why it works

Every valid number described in the problem is exactly a prefix sum of the ordered prime sequence beginning at 2. The algorithm enumerates all such prefix sums in increasing order and checks which ones are prime. Since no valid prefix sum is skipped and the largest valid prime prefix sum encountered is stored, the returned value is precisely the largest prime less than or equal to n that can be expressed as the sum of consecutive primes starting from 2.

Python Solution

from typing import List

class Solution:
    def largestPrime(self, n: int) -> int:
        if n < 2:
            return 0

        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False

        p = 2
        while p * p <= n:
            if is_prime[p]:
                for multiple in range(p * p, n + 1, p):
                    is_prime[multiple] = False
            p += 1

        primes = []
        for num in range(2, n + 1):
            if is_prime[num]:
                primes.append(num)

        prefix_sum = 0
        answer = 0

        for prime in primes:
            prefix_sum += prime

            if prefix_sum > n:
                break

            if is_prime[prefix_sum]:
                answer = prefix_sum

        return answer

The implementation begins by handling the special case where n < 2. In such situations no prime answer exists, so we return 0.

Next, a standard Sieve of Eratosthenes constructs a boolean array is_prime. After the sieve completes, is_prime[x] instantly tells us whether x is prime.

The code then extracts all primes into the primes list. These primes are already sorted because we scan the sieve in increasing order.

The main loop maintains a running prefix sum. Each new value represents the sum of consecutive primes beginning with 2. Once this sum exceeds n, the loop stops because subsequent sums can only become larger.

Whenever a prefix sum is prime according to the sieve, we update the answer. Since the prefix sums are processed in increasing order, the final stored value is the largest valid one.

Go Solution

func largestPrime(n int) int {
	if n < 2 {
		return 0
	}

	isPrime := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		isPrime[i] = true
	}

	for p := 2; p*p <= n; p++ {
		if isPrime[p] {
			for multiple := p * p; multiple <= n; multiple += p {
				isPrime[multiple] = false
			}
		}
	}

	primes := make([]int, 0)
	for i := 2; i <= n; i++ {
		if isPrime[i] {
			primes = append(primes, i)
		}
	}

	prefixSum := 0
	answer := 0

	for _, prime := range primes {
		prefixSum += prime

		if prefixSum > n {
			break
		}

		if isPrime[prefixSum] {
			answer = prefixSum
		}
	}

	return answer
}

The Go implementation follows exactly the same strategy. A boolean slice stores sieve results, and a slice of integers stores all generated primes.

No special handling for integer overflow is necessary because the maximum value involved is bounded by 500,000, which easily fits within Go's int type on all supported platforms.

Worked Examples

Example 1

Input: n = 20

Prime numbers up to 20:

Prime	Running Sum	Prime Sum?	Answer
2	2	Yes	2
3	5	Yes	5
5	10	No	5
7	17	Yes	17
11	28	Exceeds n	Stop

The largest valid prime sum is 17.

Output: 17

Example 2

Input: n = 2

Prime numbers up to 2:

Prime	Running Sum	Prime Sum?	Answer
2	2	Yes	2

No more primes remain.

Output: 2

Additional Example

Input: n = 10

Prime numbers up to 10:

Prime	Running Sum	Prime Sum?	Answer
2	2	Yes	2
3	5	Yes	5
5	10	No	5

The largest valid prime sum not exceeding 10 is 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log log n)	Sieve construction dominates the running time
Space	O(n)	Boolean sieve array of size n + 1

The Sieve of Eratosthenes runs in O(n log log n) time. Extracting the prime list and scanning the prefix sums are both linear operations and do not change the overall complexity. The sieve array requires O(n) memory.

Test Cases

sol = Solution()

assert sol.largestPrime(20) == 17      # example 1
assert sol.largestPrime(2) == 2        # example 2

assert sol.largestPrime(1) == 0        # below smallest prime
assert sol.largestPrime(3) == 2        # only prefix sum 2 fits
assert sol.largestPrime(5) == 5        # second prime prefix sum
assert sol.largestPrime(10) == 5       # 10 is not prime
assert sol.largestPrime(17) == 17      # exact prime prefix sum
assert sol.largestPrime(18) == 17      # answer just below n
assert sol.largestPrime(28) == 17      # 28 is composite
assert sol.largestPrime(29) == 17      # next valid prime sum not reached

assert sol.largestPrime(100) == 41     # larger prefix-sum case
assert sol.largestPrime(500000) > 0    # upper constraint stress test

Test Summary

Test	Why
n = 20	Verifies first sample
n = 2	Verifies smallest valid prime
n = 1	No valid answer exists
n = 3	Prefix sum exceeds limit quickly
n = 5	Second prime prefix sum
n = 10	Composite prefix sum must be ignored
n = 17	Exact valid answer equals n
n = 18	Largest answer below n
n = 28	Composite cumulative sum
n = 29	Ensures only valid prime prefix sums count
n = 100	Medium-sized verification
n = 500000	Maximum constraint stress test

Edge Cases

Very Small Input

When n = 1, there are no prime numbers less than or equal to n. A buggy implementation might attempt to access sieve indices that do not exist or incorrectly return 1 as a prime. The solution explicitly checks n < 2 and returns 0.

Prefix Sum Equals n

If a prime prefix sum is exactly equal to n, it must be considered valid because the requirement is "less than or equal to n". For example, when n = 17, the cumulative sum 2 + 3 + 5 + 7 = 17 should be returned. The implementation only stops when prefix_sum > n, ensuring equality is accepted.

Composite Prefix Sums

Many cumulative prime sums are not themselves prime. For example, 2 + 3 + 5 = 10. A common mistake would be to assume every cumulative prime sum is valid. The algorithm avoids this by checking every prefix sum against the sieve before updating the answer.

Early Termination

Once a prefix sum exceeds n, all future prefix sums will also exceed n because primes are positive numbers. A buggy implementation might continue scanning unnecessarily. The solution immediately breaks out of the loop, improving efficiency while preserving correctness.

No Large Valid Candidate

There may be long stretches where several consecutive prefix sums are composite. The algorithm does not assume recent sums are valid. Instead, it continuously tracks the last prime prefix sum encountered, ensuring the final answer remains correct even when many later prefix sums fail the primality check.