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 <= 106
Problem Overview: You are given two integers left and right. The task is to find two prime numbers within this inclusive range whose difference is the smallest among all prime pairs in the range. If fewer than two primes exist, return [-1, -1].
Approach 1: Direct Prime Check with Iteration (Time: O((R-L) * sqrt(R)), Space: O(1))
Iterate through every number from left to right and check whether it is prime. A number is prime if it has no divisors from 2 to sqrt(n). Keep track of the previous prime encountered and compute the difference with the current prime. Update the best pair whenever you find a smaller gap. This approach relies purely on arithmetic checks and constant memory, making it simple to implement when the range size is small. It directly uses concepts from math and number theory.
Approach 2: Sieve of Eratosthenes Optimization (Time: O(n log log n), Space: O(n))
Generate all prime numbers up to right using the Sieve of Eratosthenes. Create a boolean array where each index represents whether the number is prime. Start with all numbers marked prime, then mark multiples of each prime starting from 2. After building the sieve, iterate from left to right and collect primes or compare them on the fly. Track the previous prime and update the smallest difference pair. This avoids repeated square root checks and is significantly faster for large ranges.
Recommended for interviews: Start with the direct prime check to demonstrate understanding of primality testing. Interviewers usually expect the optimized approach using the sieve when the range becomes large. The sieve shows familiarity with classic number theory techniques and reduces repeated work, making it the practical solution for competitive programming and system constraints.
This approach involves iterating through each number in the given range and checking if it is a prime number by testing divisibility from 2 up to the square root of the number. After identifying prime numbers, the algorithm tracks the pair with the minimum difference.
This C solution uses a helper function is_prime to check if a number is prime. It loops over each number in the range and records the closest prime pair.
Time Complexity: O(n*sqrt(m)) where n is the range size and m is the number being checked for primality.
Space Complexity: O(1)
This approach leverages the Sieve of Eratosthenes, a well-known algorithm for finding all prime numbers up to a given limit. It marks non-prime numbers in a boolean array, making subsequent queries to check if a number is prime efficient. After sieving up to the right range boundary, the solution checks the range and identifies the closest prime numbers.
This C solution incorporates the Sieve of Eratosthenes to preprocess primes up to the right boundary, then checks the range for the closest prime pair.
Time Complexity: O(n log log n) for sieving, plus O(d) for checking range where d is the difference between left and right.
Space Complexity: O(n) for storing prime markers.
For the given range [left, right], we can use the linear sieve method to find all prime numbers. Then, we traverse the prime numbers in ascending order to find the pair of adjacent prime numbers with the smallest difference, which will be the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n = right.
| Approach | Complexity |
|---|---|
| Direct Prime Check with Iteration | Time Complexity: O(n*sqrt(m)) where n is the range size and m is the number being checked for primality. |
| Sieve of Eratosthenes Optimization | Time Complexity: O(n log log n) for sieving, plus O(d) for checking range where d is the difference between left and right. |
| Linear Sieve | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Prime Check with Iteration | O((R-L) * sqrt(R)) | O(1) | Small ranges or when avoiding extra memory |
| Sieve of Eratosthenes | O(n log log n) | O(n) | Large ranges where repeated prime checks are expensive |
Closest Prime Numbers in Range - Leetcode 2523 - Python • NeetCodeIO • 9,264 views views
Watch 9 more video solutions →Practice Closest Prime Numbers in Range with our built-in code editor and test cases.
Practice on FleetCode