Is Largest Prime from Consecutive Prime Sum easy or hard?

The problem is generally considered medium difficulty. Generating primes alone is straightforward, but combining sieve preprocessing, prefix sums, and binary search to efficiently evaluate consecutive ranges requires solid algorithm design skills.

Largest Prime from Consecutive Prime Sum Python/Java solution

Implementations in Python, Java, C++, Go, and TypeScript follow the same structure: generate primes using the sieve, build a prefix sum array, then iterate over start indices while binary searching the farthest valid end index. Each candidate sum is checked using the sieve lookup.

How to solve Largest Prime from Consecutive Prime Sum in O(n)?

A near-linear solution relies on preprocessing. First compute all primes with the Sieve of Eratosthenes and store them in an array. Build a prefix sum array so any consecutive sum can be computed in O(1). Then use binary search to find the largest valid range for each start and verify primality using the sieve table.

What is the best approach for Largest Prime from Consecutive Prime Sum?

The most efficient method uses preprocessing with the Sieve of Eratosthenes to generate primes, followed by a prefix sum array for constant-time range sums. For each starting index, binary search finds the farthest valid end index. This reduces repeated computations and runs in roughly O(N log log N + P log P) time.

Is Largest Prime from Consecutive Prime Sum asked at Google/Amazon/Meta?

Problems involving prime preprocessing, prefix sums, and range queries commonly appear in interviews at companies like Google, Amazon, and Meta. Variants of consecutive prime sum problems are frequently used to test number theory knowledge and algorithmic optimization skills.

What data structure is used in Largest Prime from Consecutive Prime Sum?

The solution typically uses arrays for the sieve and prefix sums. The sieve array stores primality information, while the prefix sum array enables constant-time computation of sums of consecutive primes. Binary search operates on these arrays to efficiently locate valid ranges.

What is the time complexity of Largest Prime from Consecutive Prime Sum?

Using the optimal approach, generating primes with the sieve takes O(N log log N). Building prefix sums takes O(P), and each starting position performs a binary search in O(log P). The total complexity is approximately O(N log log N + P log P) with O(N) space.

Description Hints 3 Solution Video 11:48

3770. Largest Prime from Consecutive Prime Sum

Medium39.0% acceptance2 companies

You are given an integer n.

Return the largest prime number less than or equal to n that can be expressed as the sum of one or more consecutive prime numbers starting from 2. If no such number exists, return 0.

Example 1:

Input: n = 20

Output: 17

Explanation:

The prime numbers less than or equal to n = 20 which are consecutive prime sums are:

2 = 2
5 = 2 + 3
17 = 2 + 3 + 5 + 7

The largest is 17, so it is the answer.

Example 2:

Input: n = 2

Output: 2

Explanation:

The only consecutive prime sum less than or equal to 2 is 2 itself.

Constraints:

1 <= n <= 5 * 10⁵

Asked at 2 companies

Google Meta

Topics

Hints open one at a time

Hint 1

Generate all prime numbers up to n (use sieve or trial division).

Hint 2

Compute consecutive sums starting from 2 until the sum exceeds n.

Hint 3

Find the largest sum that is also a prime.

11:48

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def largestPrime(self, n: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution