Given two positive integers left and right, find the two integers num1 and num2 such that:
left <= nums1 < nums2 <= right.nums1andnums2are both prime numbers.nums2 - nums1is 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
<style type="text/css">.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0; } .spoiler {overflow:hidden;} .spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;} .spoilerbutton[value="Show Message"] + .spoiler > div {margin-top:-500%;} .spoilerbutton[value="Hide Message"] + .spoiler {padding:5px;} </style>
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 ansclass 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;
}
};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
}