NeetCode #935LC-2523MediumMath & Geometry
← Back to All Problems#935 · #2523 · Closest Prime Numbers in Range(范围内最接近的两个质数)
📌 Problem Statement & Constraints
Given two integers
left and right, find two primes p1 < p2 in [left, right] with the smallest difference. Return [p1, p2], or [-1, -1] if fewer than two primes exist. Constraints: 1 <= left <= right <= 10^6.💡 Core Algorithmic Approaches
- Sieve all primes up to
rightwith the Sieve of Eratosthenes. - Scan the range in increasing order and remember the previous prime seen.
- The globally closest pair must be adjacent in the sorted prime sequence, so only consecutive primes need comparing.
- Track the smallest gap; if fewer than two primes appear, return
[-1, -1].
💻 Benchmark Python3 Implementation
class Solution:
def closestPrimes(self, left: int, right: int) -> List[int]:
is_prime = [True] * (right + 1)
is_prime[0] = False
if right >= 1:
is_prime[1] = False
for i in range(2, int(right ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, right + 1, i):
is_prime[j] = False
prev = -1
best = [-1, -1]
best_gap = float("inf")
for p in range(left, right + 1):
if is_prime[p]:
if prev != -1 and p - prev < best_gap:
best_gap = p - prev
best = [prev, p]
prev = p
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(right log log right): the sieve dominates.
💾 Space Complexity
O(right): the sieve array.
⚠️ Interview Pitfalls & Follow-ups
- Comparing non-adjacent primes: in the sorted sequence of primes, the minimum difference is always between two consecutive primes.
- Assuming
left >= 2:leftcan be 1, so index 1 must be marked composite before scanning. - Testing each number for primality separately: O((right - left) * sqrt(right)) is far too slow for the bounds.
- Returning an empty list when no pair exists: the required sentinel is
[-1, -1].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.