2523. Closest Prime Numbers in Range - Detailed Explanation

Problem Statement

Given two integers left and right, find two prime numbers within the inclusive range [left, right] that are closest to each other. In other words, if there exist two primes p₁ and p₂ in the range such that p₁ < p₂ and the difference (p₂ - p₁) is minimized, return the pair as [p₁, p₂]. If no such pair exists (for example, if there is less than two primes in the range), return [-1, -1].

Example 1

• Input: left = 10, right = 19
• Output: [11, 13]
• Explanation:
  The prime numbers in the range are [11, 13, 17, 19]. The pair (11, 13) has the smallest difference of 2.

Example 2

• Input: left = 4, right = 6
• Output: [-1, -1]
• Explanation:
  There is only one prime number (5) in the range, so no pair exists.

Example 3

• Input: left = 1, right = 2
• Output: [-1, -1]
• Explanation:
  Even though 2 is prime, 1 is not prime, so there is only one prime in the range.

Constraints

• 1 <= left <= right <= 10⁶
• The range [left, right] can be large, so an efficient approach is necessary.

Hints

1. Prime Generation:
   To efficiently identify primes in the range, consider using the Sieve of Eratosthenes. This will allow you to precompute prime numbers up to right in O(n log log n) time.

2. Iterating Over Primes:
   Once you have a list (or a boolean array) of prime indicators, iterate through the range [left, right] and track consecutive primes. Compute the difference between each pair and update the closest pair accordingly.

Approach 1: Brute Force (Not Recommended)

Explanation

A straightforward solution is to check each number in the range [left, right] to see if it is prime by testing divisibility by every number up to its square root. Then, iterate over the list of found primes to determine the pair with the minimum difference.

Step-by-Step Walkthrough

1. For each number in the range [left, right], check if it is prime.
2. Store the primes in a list.
3. If the list contains fewer than two primes, return [-1, -1].
4. Iterate over the list of primes to find the pair with the smallest difference.

Drawbacks

• Checking each number individually for primality in a large range is inefficient.
• The worst-case time complexity can be high when the range is large.

Approach 2: Sieve of Eratosthenes (Optimal In-Place Prime Generation)

Explanation

A much more efficient approach involves using the Sieve of Eratosthenes to generate all prime numbers up to right. This method precomputes prime status for every number up to right in one go, allowing you to then simply iterate through the range [left, right] to extract the primes.

Steps Involved

1. Sieve Setup:

   • Create a boolean array sieve of size right + 1 where each element initially indicates that the number is prime.
   • Mark 0 and 1 as non-prime.

2. Sieve Execution:

   • For every number i from 2 to √right, if i is marked prime, mark all multiples of i starting from i² as non-prime.

3. Finding the Closest Pair:

   • Initialize a variable prev to track the previous prime encountered.
   • Iterate from left to right. For each number, if it is prime:
     • If prev is not -1, compute the difference between the current prime and prev.
     • Update the best (smallest) difference and the corresponding pair if the current difference is smaller.
     • Update prev to the current prime.

4. Return the Result:

   • If no pair is found, return [-1, -1]. Otherwise, return the best pair.

Step-by-Step Walkthrough

Consider left = 10 and right = 19:

1. Sieve Generation:

   • Generate a boolean array where primes up to 19 are marked true.
   • Primes in the range: 11, 13, 17, 19.

2. Finding the Pair:

   • Initialize prev = -1.
   • Iterate over each number from 10 to 19:
     • 10: not prime.
     • 11: prime, set prev = 11.
     • 12: not prime.
     • 13: prime, difference = 13 - 11 = 2, update best pair to [11, 13], set prev = 13.
     • 14, 15, 16: not prime.
     • 17: prime, difference = 17 - 13 = 4, no update, set prev = 17.
     • 18: not prime.
     • 19: prime, difference = 19 - 17 = 2, but the best difference remains 2; update prev = 19.
   • The closest pair remains [11, 13].

Complexity Analysis

• Time Complexity:

  • Sieve of Eratosthenes runs in O(n log log n) where n = right.
  • Iterating from left to right is O(n).
  • Overall, the solution is efficient for the given constraints.

• Space Complexity:

  • O(n) for the sieve array.

Python Code