Given two positive integers left
and right
, find the two integers num1
and num2
such that:
left <= nums1 < nums2 <= right
.nums1
andnums2
are both prime numbers.nums2 - nums1
is the minimum amongst all other pairs satisfying the above conditions.
Return the positive integer array ans = [nums1, nums2]
. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1
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
Solution: Sieve of Eratosthenes

Use Sieve of Eratosthenes to find all primes in range [0, right].
Check neighbor primes and find the best pair.
Time complexity: O(nloglogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: vector<int> closestPrimes(int left, int right) { vector<int> primes(right + 1, 1); primes[0] = primes[1] = 0; for (int i = 2; i <= sqrt(right); ++i) { if (!primes[i]) continue; for (int x = i * i; x <= right; x += i) primes[x] = 0; } vector<int> ans{-1,-1}; for (int i = left, last = -1, best = INT_MAX; i <= right; ++i) { if (!primes[i]) continue; if (last > 0 && i - last < best) { best = i - last; ans = {last, i}; } last = i; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment