Question

2523. Closest Prime Numbers in Range

中文文档

Description

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

 

Solutions

Solution 1

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

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;
  }
};

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
}