LeetCode Solutions Blog

Closest Prime Numbers in Range

Number: 2610

Difficulty: Medium

Paid? No

Problem Description

Given two positive integers left and right, identify two prime numbers num1 and num2 in the range [left, right] such that num2 - num1 is minimized. If there are multiple pairs with the same minimum difference, choose the pair with the smallest num1. If no such pair exists, return [-1, -1].

Key Insights

Use the Sieve of Eratosthenes to efficiently generate all prime numbers up to right.
Iterate only over the range from max(left, 2) to right to locate the primes.
Track the previous encountered prime and update the best pair when a smaller gap between consecutive primes is found.
Choose the pair with the smallest first prime in case of ties.

Space and Time Complexity

Time Complexity: O(n log log n) due to the Sieve of Eratosthenes, where n is right.
Space Complexity: O(n) for the sieve array.

Solution

The solution uses the Sieve of Eratosthenes to mark all prime numbers up to right. Starting from max(left, 2), we iterate through the range and identify primes. For each prime found, if we have a previous prime, we compute the gap and update the best pair if the gap is smaller than the current best. Finally, we return the best pair or [-1, -1] if less than two primes exist in the range.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to find the closest prime pair in the range [left, right]
def closest_primes(left, right):
    # Initialize the sieve with True values for indices 0...right
    sieve = [True] * (right + 1)
    # Mark 0 and 1 as non-prime
    if right >= 0:
        sieve[0] = False
    if right >= 1:
        sieve[1] = False

    # Sieve of Eratosthenes: mark non-prime numbers
    p = 2
    while p * p <= right:
        if sieve[p]:
            # Mark multiples of p as non-prime
            for multiple in range(p * p, right + 1, p):
                sieve[multiple] = False
        p += 1

    best_gap = float("inf")   # Initialize the best gap as infinity
    best_pair = [-1, -1]      # Default result if no pair is found
    previous_prime = -1       # Variable to store the last encountered prime

    # Iterate over the range starting from max(left, 2)
    for number in range(max(left, 2), right + 1):
        if sieve[number]:
            # If a previous prime exists, compute the gap
            if previous_prime != -1:
                gap = number - previous_prime
                if gap < best_gap:
                    best_gap = gap
                    best_pair = [previous_prime, number]
            # Update the previous prime
            previous_prime = number

    return best_pair

# Example usage
if __name__ == "__main__":
    left = 10
    right = 19
    print(closest_primes(left, right))  # Expected output: [11, 13]