Closest Prime Numbers in Range

medium math number theory sieve

Problem

Given two positive integers left and right, find primes num1 and num2 with left ≤ num1 < num2 ≤ right such that num2 − num1 is the minimum over all valid prime pairs. Return [num1, num2]; on ties pick the smallest num1. If no such pair exists, return [-1, -1].

Inputleft = 10, right = 19

Output[11, 13]

Primes in range are 11, 13, 17, 19. The smallest gap is 2, met by [11,13] and [17,19]; since 11 < 17 we return [11,13].

left

right

def closestPrimes(left, right):
    # Sieve of Eratosthenes: mark primes up to right
    is_prime = [True] * (right + 1)
    is_prime[0] = False
    if right >= 1:
        is_prime[1] = False
    i = 2
    while i * i <= right:
        if is_prime[i]:
            for j in range(i * i, right + 1, i):
                is_prime[j] = False
        i += 1
    # scan consecutive primes in [left, right] for the smallest gap
    prev = -1
    ans = [-1, -1]
    best = float("inf")
    for n in range(left, right + 1):
        if is_prime[n]:
            if prev != -1 and n - prev < best:
                best = n - prev
                ans = [prev, n]
            prev = n
    return ans

function closestPrimes(left, right) {
  // Sieve of Eratosthenes: mark primes up to right
  const isPrime = new Array(right + 1).fill(true);
  isPrime[0] = false;
  if (right >= 1) isPrime[1] = false;
  for (let i = 2; i * i <= right; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= right; j += i) isPrime[j] = false;
    }
  }
  // scan consecutive primes in [left, right] for the smallest gap
  let prev = -1, best = Infinity;
  let ans = [-1, -1];
  for (let n = left; n <= right; n++) {
    if (isPrime[n]) {
      if (prev !== -1 && n - prev < best) {
        best = n - prev;
        ans = [prev, n];
      }
      prev = n;
    }
  }
  return ans;
}

int[] closestPrimes(int left, int right) {
    // Sieve of Eratosthenes: mark primes up to right
    boolean[] isPrime = new boolean[right + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    if (right >= 1) isPrime[1] = false;
    for (int i = 2; i * i <= right; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= right; j += i) isPrime[j] = false;
        }
    }
    // scan consecutive primes in [left, right] for the smallest gap
    int prev = -1, best = Integer.MAX_VALUE;
    int[] ans = {-1, -1};
    for (int n = left; n <= right; n++) {
        if (isPrime[n]) {
            if (prev != -1 && n - prev < best) {
                best = n - prev;
                ans = new int[]{prev, n};
            }
            prev = n;
        }
    }
    return ans;
}

vector<int> closestPrimes(int left, int right) {
    // Sieve of Eratosthenes: mark primes up to right
    vector<bool> isPrime(right + 1, true);
    isPrime[0] = false;
    if (right >= 1) isPrime[1] = false;
    for (int i = 2; i * i <= right; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= right; j += i) isPrime[j] = false;
        }
    }
    // scan consecutive primes in [left, right] for the smallest gap
    int prev = -1, best = INT_MAX;
    vector<int> ans = {-1, -1};
    for (int n = left; n <= right; n++) {
        if (isPrime[n]) {
            if (prev != -1 && n - prev < best) {
                best = n - prev;
                ans = {prev, n};
            }
            prev = n;
        }
    }
    return ans;
}

Explanation

The pair we want is always made of two consecutive primes. If two primes are adjacent in the sorted list of primes, nothing sits between them, so their gap is as small as any gap involving either of them. That means we never have to compare every pair — only neighbours.

To know which numbers are prime, we run the Sieve of Eratosthenes once up to right. Start by assuming every number is prime, mark 0 and 1 as not prime, then for each prime i cross off its multiples starting at i*i. After the sieve, is_prime[n] answers primality in O(1).

Now walk n from left to right. Keep prev, the previous prime we saw. Whenever we hit a prime and already have a prev, the gap n - prev is a candidate. If it beats the best gap so far, record [prev, n]. Because we scan left to right and only update on a strictly smaller gap, the first pair achieving the minimum — the one with the smallest num1 — is the one we keep.

If fewer than two primes lie in the range, ans stays [-1, -1], which is exactly the required answer.

Example: left = 10, right = 19. Primes found are 11, 13, 17, 19. Gaps are 13−11 = 2, 17−13 = 4, 19−17 = 2. The first gap of 2 gives [11, 13].

Time: O(right · log log right) Space: O(right)