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
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Closest Prime Numbers in Range - Leetcode 2523 - Python • NeetCodeIO • 8,496 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