2523. Closest Prime Numbers in Range - Solution

Q: Is Closest Prime Numbers in Range easy or hard?

Closest Prime Numbers in Range is typically classified as a Medium problem. The logic is straightforward once you recognize that generating primes efficiently with the Sieve of Eratosthenes avoids repeated expensive primality checks.

Q: Closest Prime Numbers in Range Python/Java solution

Both Python and Java implementations follow the same logic: either check primality for each number using a sqrt loop or build a sieve array up to the upper bound. After identifying primes, maintain the previous prime and update the pair with the smallest difference.

Q: How to solve Closest Prime Numbers in Range in O(n)?

An O(n) style scan is achieved after preprocessing primes with the Sieve of Eratosthenes. Build the sieve up to the maximum value, then iterate through the range once while keeping track of the previous prime and updating the smallest difference pair.

Q: What is the best approach for Closest Prime Numbers in Range?

The most efficient approach is using the Sieve of Eratosthenes to precompute all primes up to the upper bound of the range. After generating primes, scan from left to right and track the pair with the smallest difference. This runs in O(n log log n) time and avoids repeated primality checks.

Q: Is Closest Prime Numbers in Range asked at Google/Amazon/Meta?

Prime number and number theory problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving prime generation, sieve techniques, or range-based prime queries are common in coding interviews and competitive programming.

Q: What data structure is used in Closest Prime Numbers in Range?

The optimized solution uses a boolean array (or bitset) to represent whether each number is prime in the Sieve of Eratosthenes. The algorithm also tracks the previous prime value while iterating through the range to compute differences.

Q: What is the time complexity of Closest Prime Numbers in Range?

The direct iteration approach checks each number for primality in O(sqrt(n)), giving roughly O((R-L) * sqrt(R)) time. Using the Sieve of Eratosthenes reduces the complexity to O(n log log n) for preprocessing plus O(n) scanning, which is typically faster for large ranges.

The problem

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 <= 10⁶

Approach overview

Problem Overview: You are given two integers left and right. The task is to find two prime numbers within this inclusive range whose difference is the smallest among all prime pairs in the range. If fewer than two primes exist, return [-1, -1].

Approach 1: Direct Prime Check with Iteration (Time: O((R-L) * sqrt(R)), Space: O(1))

Iterate through every number from left to right and check whether it is prime. A number is prime if it has no divisors from 2 to sqrt(n). Keep track of the previous prime encountered and compute the difference with the current prime. Update the best pair whenever you find a smaller gap. This approach relies purely on arithmetic checks and constant memory, making it simple to implement when the range size is small. It directly uses concepts from math and number theory.

Approach 2: Sieve of Eratosthenes Optimization (Time: O(n log log n), Space: O(n))

Generate all prime numbers up to right using the Sieve of Eratosthenes. Create a boolean array where each index represents whether the number is prime. Start with all numbers marked prime, then mark multiples of each prime starting from 2. After building the sieve, iterate from left to right and collect primes or compare them on the fly. Track the previous prime and update the smallest difference pair. This avoids repeated square root checks and is significantly faster for large ranges.

Recommended for interviews: Start with the direct prime check to demonstrate understanding of primality testing. Interviewers usually expect the optimized approach using the sieve when the range becomes large. The sieve shows familiarity with classic number theory techniques and reduces repeated work, making it the practical solution for competitive programming and system constraints.

Approach 1: Direct Prime Check with Iteration

This approach involves iterating through each number in the given range and checking if it is a prime number by testing divisibility from 2 up to the square root of the number. After identifying prime numbers, the algorithm tracks the pair with the minimum difference.

Python

import sys

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def closest_primes(left, right):
    prev = -1
    min_diff = sys.maxsize
    result = [-1, -1]
    for i in range(left, right + 1):
        if is_prime(i):
            if prev != -1 and (i - prev) < min_diff:
                min_diff = i - prev
                result = [prev, i]
            prev = i
    return result

if __name__ == "__main__":
    left, right = 10, 19
    result = closest_primes(left, right)
    print(result)

Java

public class ClosestPrimes {
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }

    public static int[] closestPrimes(int left, int right) {
        int prev = -1, minDiff = Integer.MAX_VALUE;
        int[] result = {-1, -1};
        for (int i = left; i <= right; i++) {
            if (isPrime(i)) {
                if (prev != -1 && (i - prev) < minDiff) {
                    minDiff = i - prev;
                    result[0] = prev;
                    result[1] = i;
                }
                prev = i;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int left = 10, right = 19;
        int[] result = closestPrimes(left, right);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

C++

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

pair<int, int> closestPrimes(int left, int right) {
    int prev = -1, min_diff = INT_MAX;
    pair<int, int> result = {-1, -1};
    for (int i = left; i <= right; ++i) {
        if (is_prime(i)) {
            if (prev != -1 && (i - prev) < min_diff) {
                min_diff = i - prev;
                result = {prev, i};
            }
            prev = i;
        }
    }
    return result;
}

int main() {
    int left = 10, right = 19;
    auto result = closestPrimes(left, right);
    cout << "[" << result.first << ", " << result.second << "]" << endl;
    return 0;
}

JavaScript

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

function closestPrimes(left, right) {
    let prev = -1, minDiff = Number.MAX_VALUE;
    let result = [-1, -1];
    for (let i = left; i <= right; i++) {
        if (isPrime(i)) {
            if (prev !== -1 && (i - prev) < minDiff) {
                minDiff = i - prev;
                result = [prev, i];
            }
            prev = i;
        }
    }
    return result;
}

const left = 10, right = 19;
console.log(closestPrimes(left, right));

#include <stdio.h>
#include <math.h>
#include <limits.h>

int is_prime(int n) {
    if (n <= 1) return 0;
    if (n <= 3) return 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    }
    return 1;
}

void closestPrimes(int left, int right, int *result) {
    int prev = -1, min_diff = INT_MAX;
    result[0] = result[1] = -1;
    for (int i = left; i <= right; ++i) {
        if (is_prime(i)) {
            if (prev != -1 && (i - prev) < min_diff) {
                min_diff = i - prev;
                result[0] = prev;
                result[1] = i;
            }
            prev = i;
        }
    }
}

int main() {
    int left = 10, right = 19;
    int result[2];
    closestPrimes(left, right, result);
    printf("[%d, %d]\n", result[0], result[1]);
    return 0;
}

using System;

public class Program {
    public static bool IsPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }

    public static int[] ClosestPrimes(int left, int right) {
        int prev = -1, minDiff = int.MaxValue;
        int[] result = {-1, -1};
        for (int i = left; i <= right; i++) {
            if (IsPrime(i)) {
                if (prev != -1 && (i - prev) < minDiff) {
                    minDiff = i - prev;
                    result[0] = prev;
                    result[1] = i;
                }
                prev = i;
            }
        }
        return result;
    }

    public static void Main() {
        int left = 10, right = 19;
        int[] result = ClosestPrimes(left, right);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

This Python solution leverages a function to check for primes, iterating through the range to identify the smallest difference between consecutive primes.

Complexity

Time Complexity: O(n*sqrt(m)) where n is the range size and m is each number being checked.
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Sieve of Eratosthenes Optimization

This approach leverages the Sieve of Eratosthenes, a well-known algorithm for finding all prime numbers up to a given limit. It marks non-prime numbers in a boolean array, making subsequent queries to check if a number is prime efficient. After sieving up to the right range boundary, the solution checks the range and identifies the closest prime numbers.

Python

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for start in range(2, int(n**0.5) + 1):
        if is_prime[start]:
            for multiple in range(start*start, n + 1, start):
                is_prime[multiple] = False
    return is_prime


def closest_primes(left, right):
    is_prime = sieve_of_eratosthenes(right)
    prev = -1
    min_diff = float('inf')
    result = [-1, -1]
    for i in range(left, right + 1):
        if is_prime[i]:
            if prev != -1 and (i - prev) < min_diff:
                min_diff = i - prev
                result = [prev, i]
            prev = i
    return result

if __name__ == "__main__":
    left, right = 10, 19
    result = closest_primes(left, right)
    print(result)

Java

import java.util.Arrays;

public class ClosestPrimes {

    public static void sieveOfEratosthenes(boolean[] isPrime, int n) {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    public static int[] closestPrimes(int left, int right) {
        boolean[] isPrime = new boolean[right + 1];
        sieveOfEratosthenes(isPrime, right);
        int prev = -1, minDiff = Integer.MAX_VALUE;
        int[] result = {-1, -1};
        for (int i = left; i <= right; i++) {
            if (isPrime[i]) {
                if (prev != -1 && (i - prev) < minDiff) {
                    minDiff = i - prev;
                    result[0] = prev;
                    result[1] = i;
                }
                prev = i;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int left = 10, right = 19;
        int[] result = closestPrimes(left, right);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

void sieve_of_eratosthenes(vector<bool> &is_prime, int n) {
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
}

pair<int, int> closestPrimes(int left, int right) {
    vector<bool> is_prime(right + 1, true);
    is_prime[0] = is_prime[1] = false;
    sieve_of_eratosthenes(is_prime, right);
    
    int prev = -1, min_diff = INT_MAX;
    pair<int, int> result = {-1, -1};
    for (int i = left; i <= right; i++) {
        if (is_prime[i]) {
            if (prev != -1 && (i - prev) < min_diff) {
                min_diff = i - prev;
                result = {prev, i};
            }
            prev = i;
        }
    }
    return result;
}

int main() {
    int left = 10, right = 19;
    auto result = closestPrimes(left, right);
    cout << "[" << result.first << ", " << result.second << "]" << endl;
    return 0;
}

JavaScript

function sieveOfEratosthenes(n) {
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

function closestPrimes(left, right) {
    const isPrime = sieveOfEratosthenes(right);
    let prev = -1, minDiff = Number.MAX_VALUE;
    let result = [-1, -1];
    for (let i = left; i <= right; i++) {
        if (isPrime[i]) {
            if (prev !== -1 && (i - prev) < minDiff) {
                minDiff = i - prev;
                result = [prev, i];
            }
            prev = i;
        }
    }
    return result;
}

const left = 10, right = 19;
console.log(closestPrimes(left, right));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void sieve_of_eratosthenes(int *is_prime, int n) {
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i] == 1) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = 0;
        }
    }
}

void closestPrimes(int left, int right, int *result) {
    int *is_prime = malloc((right + 1) * sizeof(int));
    for (int i = 0; i <= right; i++) {
        is_prime[i] = (i < 2) ? 0 : 1;
    }
    
    sieve_of_eratosthenes(is_prime, right);
    
    int prev = -1, min_diff = INT_MAX;
    result[0] = result[1] = -1;
    for (int i = left; i <= right; i++) {
        if (is_prime[i]) {
            if (prev != -1 && (i - prev) < min_diff) {
                min_diff = i - prev;
                result[0] = prev;
                result[1] = i;
            }
            prev = i;
        }
    }
    free(is_prime);
}

int main() {
    int left = 10, right = 19;
    int result[2];
    closestPrimes(left, right, result);
    printf("[%d, %d]\n", result[0], result[1]);
    return 0;
}

using System;

public class Program {
    public static bool[] SieveOfEratosthenes(int n) {
        bool[] isPrime = new bool[n + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            }
        }
        return isPrime;
    }

    public static int[] ClosestPrimes(int left, int right) {
        var isPrime = SieveOfEratosthenes(right);
        int prev = -1, minDiff = int.MaxValue;
        int[] result = new int[] {-1, -1};
        for (int i = left; i <= right; i++) {
            if (isPrime[i]) {
                if (prev != -1 && (i - prev) < minDiff) {
                    minDiff = i - prev;
                    result[0] = prev;
                    result[1] = i;
                }
                prev = i;
            }
        }
        return result;
    }

    public static void Main() {
        int left = 10, right = 19;
        int[] result = ClosestPrimes(left, right);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

In Python, the solution uses a list to mark non-prime numbers via a sieve approach, thereafter finding the closest primes in the range.

Complexity

Time Complexity: O(n log log n) for the sieve process with additional O(d) for checking primes in the range.
Space Complexity: O(n).

Try this approach in the editor

Approach 3: Linear Sieve

For the given range [left, right], we can use the linear sieve method to find all prime numbers. Then, we traverse the prime numbers in ascending order to find the pair of adjacent prime numbers with the smallest difference, which will be the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n = right.

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Direct Prime Check with Iteration	Time Complexity: O(n*sqrt(m)) where n is the range size and m is each number being checked. Space Complexity: O(1)
Sieve of Eratosthenes Optimization	Time Complexity: O(n log log n) for the sieve process with additional O(d) for checking primes in the range. Space Complexity: O(n).
Linear Sieve	–

Complexity analysis

Approach	Time	Space	When to Use
Direct Prime Check with Iteration	O((R-L) * sqrt(R))	O(1)	Small ranges or when avoiding extra memory
Sieve of Eratosthenes	O(n log log n)	O(n)	Large ranges where repeated prime checks are expensive

Frequently asked questions

Is Closest Prime Numbers in Range easy or hard?

Closest Prime Numbers in Range is typically classified as a Medium problem. The logic is straightforward once you recognize that generating primes efficiently with the Sieve of Eratosthenes avoids repeated expensive primality checks.

Closest Prime Numbers in Range Python/Java solution

Both Python and Java implementations follow the same logic: either check primality for each number using a sqrt loop or build a sieve array up to the upper bound. After identifying primes, maintain the previous prime and update the pair with the smallest difference.

How to solve Closest Prime Numbers in Range in O(n)?

An O(n) style scan is achieved after preprocessing primes with the Sieve of Eratosthenes. Build the sieve up to the maximum value, then iterate through the range once while keeping track of the previous prime and updating the smallest difference pair.

What is the best approach for Closest Prime Numbers in Range?

The most efficient approach is using the Sieve of Eratosthenes to precompute all primes up to the upper bound of the range. After generating primes, scan from left to right and track the pair with the smallest difference. This runs in O(n log log n) time and avoids repeated primality checks.

Is Closest Prime Numbers in Range asked at Google/Amazon/Meta?

Prime number and number theory problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving prime generation, sieve techniques, or range-based prime queries are common in coding interviews and competitive programming.

What data structure is used in Closest Prime Numbers in Range?

The optimized solution uses a boolean array (or bitset) to represent whether each number is prime in the Sieve of Eratosthenes. The algorithm also tracks the previous prime value while iterating through the range to compute differences.

What is the time complexity of Closest Prime Numbers in Range?

The direct iteration approach checks each number for primality in O(sqrt(n)), giving roughly O((R-L) * sqrt(R)) time. Using the Sieve of Eratosthenes reduces the complexity to O(n log log n) for preprocessing plus O(n) scanning, which is typically faster for large ranges.

Closest Prime Numbers in Range solution and explanation

The problem

Approach overview

Approach 1: Direct Prime Check with Iteration

Approach 2: Sieve of Eratosthenes Optimization

Approach 3: Linear Sieve

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Closest Prime Numbers in Range solution and explanation

The problem

Approach overview

Approach 1: Direct Prime Check with Iteration

Approach 2: Sieve of Eratosthenes Optimization

Approach 3: Linear Sieve

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems