Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go

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

All Problems

All Solutions