⚡Flashcard Drill➔
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

  1. Sieve all primes up to right with the Sieve of Eratosthenes.
  2. Scan the range in increasing order and remember the previous prime seen.
  3. The globally closest pair must be adjacent in the sorted prime sequence, so only consecutive primes need comparing.
  4. 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: left can 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems