2610. Closest Prime Numbers in Range
My accepted Python solution to LeetCode problem 2610, Closest Prime Numbers in Range, running in 1584ms.
- Difficulty: Medium
- Python
- Runtime 1584ms
- Memory 34.7MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 1584ms, memory 34.7MB, accepted 2025-12-31.
class Solution:
def closestPrimes(self, left: int, right: int) -> List[int]:
# Sieve of Eratosthenes to find all primes up to right
def sieve(n):
if n < 2:
return []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n + 1, i):
is_prime[j] = False
return is_prime
is_prime = sieve(right)
# Collect primes in range [left, right]
primes = [i for i in range(max(2, left), right + 1) if is_prime[i]]
if len(primes) < 2:
return [-1, -1]
# Find the pair with minimum gap
min_gap = float('inf')
result = [-1, -1]
for i in range(len(primes) - 1):
gap = primes[i + 1] - primes[i]
if gap < min_gap:
min_gap = gap
result = [primes[i], primes[i + 1]]
return result