Given two positive integers left and right, find the two integers num1 and num2 such that:
left <= num1 < num2 <= right .num1 and num2 are both prime numbers.num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the minimum num1 value or [-1, -1] if such numbers do not exist.
A number greater than 1 is called prime if it is only divisible by 1 and itself.
Example 1:
Input: left = 10, right = 19 Output: [11,13] Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19. The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19]. Since 11 is smaller than 17, we return the first pair.
Example 2:
Input: left = 4, right = 6 Output: [-1,-1] Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.
Constraints:
1 <= left <= right <= 106To solve #2523 Closest Prime Numbers in Range, the key idea is to efficiently identify all prime numbers within the given interval [left, right]. A brute-force primality check for each number would be too slow for larger ranges. Instead, a more efficient approach is to use the Sieve of Eratosthenes to precompute primes up to right.
First, build a sieve array marking all prime numbers up to the upper bound. Then iterate through the numbers in the target range and collect primes. While scanning these primes, track the pair with the smallest difference between consecutive primes. If no pair exists within the range, return the default result.
This approach works well because the sieve quickly filters non-prime numbers, allowing a simple linear pass to determine the closest pair. The method balances preprocessing and scanning efficiently.
Time Complexity: roughly O(n log log n) for sieve construction and O(n) for scanning.
Space Complexity: O(n) for the sieve array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sieve of Eratosthenes + Scan for Closest Pair | O(n log log n) | O(n) |
| Brute-force Primality Check | O(n√n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Use Sieve of Eratosthenes to mark numbers that are primes.
Iterate from right to left and find pair with the minimum distance between marked numbers.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prime-related range queries and sieve-based optimizations are common interview topics at major tech companies. While the exact problem may vary, the concepts of prime generation and range processing are frequently tested.
The sieve efficiently eliminates non-prime numbers in bulk, avoiding repeated primality checks. This reduces the complexity significantly compared to checking each number individually.
A boolean array or list is commonly used to implement the Sieve of Eratosthenes. It efficiently marks composite numbers and allows quick identification of primes during the scan phase.
The optimal approach uses the Sieve of Eratosthenes to precompute all prime numbers up to the upper bound of the range. After generating primes, you scan the primes within the interval and track the pair with the smallest difference.