Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2523.html
2523. Closest Prime Numbers in Range
Description
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
Solutions
-
class Solution { public int[] closestPrimes(int left, int right) { int cnt = 0; boolean[] st = new boolean[right + 1]; int[] prime = new int[right + 1]; for (int i = 2; i <= right; ++i) { if (!st[i]) { prime[cnt++] = i; } for (int j = 0; prime[j] <= right / i; ++j) { st[prime[j] * i] = true; if (i % prime[j] == 0) { break; } } } int i = -1, j = -1; for (int k = 0; k < cnt; ++k) { if (prime[k] >= left && prime[k] <= right) { if (i == -1) { i = k; } j = k; } } int[] ans = new int[] {-1, -1}; if (i == j || i == -1) { return ans; } int mi = 1 << 30; for (int k = i; k < j; ++k) { int d = prime[k + 1] - prime[k]; if (d < mi) { mi = d; ans[0] = prime[k]; ans[1] = prime[k + 1]; } } return ans; } }
-
class Solution { public: vector<int> closestPrimes(int left, int right) { int cnt = 0; bool st[right + 1]; memset(st, 0, sizeof st); int prime[right + 1]; for (int i = 2; i <= right; ++i) { if (!st[i]) { prime[cnt++] = i; } for (int j = 0; prime[j] <= right / i; ++j) { st[prime[j] * i] = true; if (i % prime[j] == 0) { break; } } } int i = -1, j = -1; for (int k = 0; k < cnt; ++k) { if (prime[k] >= left && prime[k] <= right) { if (i == -1) { i = k; } j = k; } } vector<int> ans = {-1, -1}; if (i == j || i == -1) return ans; int mi = 1 << 30; for (int k = i; k < j; ++k) { int d = prime[k + 1] - prime[k]; if (d < mi) { mi = d; ans[0] = prime[k]; ans[1] = prime[k + 1]; } } return ans; } };
-
class Solution: def closestPrimes(self, left: int, right: int) -> List[int]: cnt = 0 st = [False] * (right + 1) prime = [0] * (right + 1) for i in range(2, right + 1): if not st[i]: prime[cnt] = i cnt += 1 j = 0 while prime[j] <= right // i: st[prime[j] * i] = 1 if i % prime[j] == 0: break j += 1 p = [v for v in prime[:cnt] if left <= v <= right] mi = inf ans = [-1, -1] for a, b in pairwise(p): if (d := b - a) < mi: mi = d ans = [a, b] return ans
-
func closestPrimes(left int, right int) []int { cnt := 0 st := make([]bool, right+1) prime := make([]int, right+1) for i := 2; i <= right; i++ { if !st[i] { prime[cnt] = i cnt++ } for j := 0; prime[j] <= right/i; j++ { st[prime[j]*i] = true if i%prime[j] == 0 { break } } } i, j := -1, -1 for k := 0; k < cnt; k++ { if prime[k] >= left && prime[k] <= right { if i == -1 { i = k } j = k } } ans := []int{-1, -1} if i == j || i == -1 { return ans } mi := 1 << 30 for k := i; k < j; k++ { d := prime[k+1] - prime[k] if d < mi { mi = d ans[0], ans[1] = prime[k], prime[k+1] } } return ans }