Closest prime numbers in range

Math Number Theory

51.7% acceptance

Feb 25, 2026

923

Given two positive integers left and right, find the two integers num1 and num2 such that: left <= num1 < num2 <= right. Both num1 and num2 are 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 smallest num1 value. If no such numbers exist, return [-1, -1].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn closest_primes(left: i32, right: i32) -> Vec<i32> {
    let n = right as usize + 1;
    let mut is_prime = vec![true; n];
    if n > 0 { is_prime[0] = false; }
    if n > 1 { is_prime[1] = false; }
    let mut i = 2usize;
    while i * i < n {
      if is_prime[i] {
        let mut j = i * i;
        while j < n {
          is_prime[j] = false;
          j += i;
        }
      }
      i += 1;
    }
    let primes: Vec<i32> = (left as usize..=right as usize)
      .filter(|&x| is_prime[x])
      .map(|x| x as i32)
      .collect();
    if primes.len() < 2 {
      return vec![-1, -1];
    }
    let mut best_gap = i32::MAX;
    let mut ans = vec![-1i32, -1];
    for w in primes.windows(2) {
      let gap = w[1] - w[0];
      if gap < best_gap {
        best_gap = gap;
        ans = vec![w[0], w[1]];
      }
    }
    ans
  }
}