# 2523. Closest Prime Numbers in Range

MediumMathNumber Theory

## Problem Description

The task is to find the pair of prime numbers `nums1` and `nums2` within a given range bounded by `left` and `right` inclusive, where `nums1 < nums2`, and the difference between `nums2` and `nums1` is the smallest possible among all prime pairs in the range. A prime number is defined as a positive integer greater than `1` that has no positive integer divisors other than `1` and itself. The resulting pair of primes should be the one with the smallest `nums1` if multiple pairs have the same minimum difference. If no such pair exists, the function should return `[-1, -1]`.

To summarize:

• We are given two integers `left` and `right` which define the boundaries of our search interval.
• We need to find two prime numbers `nums1` and `nums2` such that `left <= nums1 < nums2 <= right`.
• `nums2 - nums1` should be the smallest difference among all possible prime pairs.
• If there are several pairs with the same minimum difference, return the one with the smallest `nums1`.
• If no prime pairs are found within the range, return `[-1, -1]`.

## Intuition

The intuition behind the solution is to first find all prime numbers within the given range `[left, right]`. To achieve this efficiently, we use a sieve algorithm (the Sieve of Eratosthenes is a common choice) to mark all non-prime numbers in an array. The sieve works by iterating from `2` up to `right` and marking multiples of each prime number as composite (non-prime). To improve efficiency, the iteration stops when `prime[j] * i` exceeds `right`.

After creating the sieve, we filter out the prime numbers in the range `[left, right]` and store them in the list `p`. We then need to find the pair of consecutive primes in `p` with the smallest difference. We iterate through the list `p` and use a variable `mi` to keep track of the minimum difference found so far; we also keep track of the corresponding prime pair in the variable `ans`.

The approach can be summarized as follows:

1. Create a sieve to find all primes up to `right`.
2. Filter out the primes within the range `[left, right]`.
3. Find the consecutive primes with the minimum difference.
4. Keep track of the minimum difference and the corresponding pair of primes.
5. Return the pair with the smallest difference or `[-1, -1]` if no such pair exists.

This way, we ensure that we check for prime numbers only once and then consider the smallest difference between adjacent primes, which gives us the result efficiently.

## Solution Approach

The solution is implemented using Python, and it utilizes a combination of classic algorithms and data structures to solve the problem effectively.

### Identifying Primes - Sieve of Eratosthenes

We start by setting up an array `st` (`st` stands for status), initialized with `False`, which will hold the status of each number up to `right`, indicating whether each number is prime (`False`) or not prime (`True`). The `prime` array is used to store the prime numbers found.

To identify prime numbers, we use a variant of the Sieve of Eratosthenes:

• We iterate from `2` to `right`.
• For each number `i`, if `i` has not been marked as non-prime (`st[i]` is `False`), it is a prime number, and we store it in the `prime` array.
• We then iterate through the `prime` array using the variable `j`. For every prime number `prime[j]`, we mark its multiples as non-prime (`True` in `st`) up to `right`. If `i` is divisible by `prime[j]`, we break the inner loop because all further multiples of `i` will already be marked by smaller primes.

Once the sieve is set up, we have an array `prime` that contains all the prime numbers up to `right`.

### Filtering Primes in Range

The next step is to extract the primes that lie within the given `[left, right]` range, which is done using a simple list comprehension. We loop over the primes stored in `prime[:cnt]` (where `cnt` is the count of primes found) and include only those that are within the required range, storing them in the list `p`.

### Finding the Minimum Prime Gap

With the list `p` of primes within the range at hand, we now focus on finding the pair of consecutive primes (`nums1`, `nums2`) that has the smallest gap. We'll iterate over pairs of consecutive elements in `p` using the `pairwise` function. For each pair `(a, b)`, we compute the difference `d = b - a` and compare it to the smallest difference found so far (`mi`). If `d` is smaller, we update `mi` and record the pair as the current answer (`ans`).

### Returning the Result

After iterating through all pairs, `ans` holds the prime pair with the smallest gap, or it remains `[-1, -1]` if no such pair is found (which would be the case if `p` contains fewer than two primes). The function `closestPrimes` returns `ans`.

Here's a breakdown of the code's structure with respect to the patterns and algorithms used:

1. Initialization: Setting up the `st` and `prime` arrays for the sieve.
2. Executing the Sieve: Marking non-primes and finding primes up to `right`.
3. Filtering Primes: Using a list comprehension to gather primes between `left` and `right`.
4. Finding the Closest Primes: Iterating over pairs of primes using `pairwise` and updating the answer with the tightest pair.
5. Output: Returning the final answer which could be a pair of primes or `[-1, -1]`.

The entire operation is efficient as it does not check for primality individually for each number but rather uses the sieve to pre-compute prime numbers and then looks for the closest prime pair within the filtered list.

### Example Walkthrough

Let's walk through an example to illustrate the solution approach using a small range. Suppose we are given the range `left = 10` and `right = 20`. We want to find the pair of prime numbers `nums1` and `nums2` within this range such that `10 <= nums1 < nums2 <= 20` and `nums2 - nums1` is the smallest possible difference.

#### Step 1: Initialization

We initialize an array `st` of size `right + 1` to mark non-prime (`True`) and prime (`False`) statuses, with all values initially set to `False`, and create an empty list `prime` to store the prime numbers.

#### Step 2: Executing the Sieve

Starting with the smallest prime number, 2, we iterate through the range up to `right` (20 in this case):

• `2` is prime, so we mark all multiples of 2 (4, 6, 8, ...) as non-prime (`True`) in `st`.
• `3` is prime, so we mark all multiples of 3 (6, 9, 12, ...) as non-prime.
• This process continues until we've checked up to the prime number `5`, marking its multiples, since multiples of primes greater than `5` will exceed 20.

After executing the sieve, we can determine that the prime numbers up to `20` are `{2, 3, 5, 7, 11, 13, 17, 19}`.

#### Step 3: Filtering Primes in Range

Next, we filter the primes that are within our given range `[10, 20]`. By simply checking our prime list we get the primes within the range as `{11, 13, 17, 19}`.

#### Step 4: Finding the Minimum Prime Gap

Now we need to find the smallest gap between consecutive primes in our list, which is `{11, 13, 17, 19}`. We iterate over the list and calculate the differences:

• Difference between `13` and `11` is `2`.
• Difference between `17` and `13` is `4`.
• Difference between `19` and `17` is `2`.

We find that there are two smallest gaps of `2`: between `11` and `13` and between `17` and `19`. As the problem specifies that we should return the pair with the smallest `nums1`, the pair `11` and `13` is the solution we are looking for.

#### Step 5: Output

Our final answer is the pair `[11, 13]` with the smallest possible difference (which is `2`) among the primes in the range. Therefore, the function `closestPrimes` returns `[11, 13]`.

By following these steps, we have identified the primes within the specified range using the Sieve of Eratosthenes, filtered the prime numbers within our specified range, found the pair with the smallest gap, and returned our solution efficiently.

## Python Solution

``````1from math import inf
2from typing import List
3
4class Solution:
5    def closest_primes(self, left: int, right: int) -> List[int]:
6        # Initialize a counter for primes
7        prime_count = 0
8
9        # Initialize a list to mark non-prime numbers
10        sieve = [False] * (right + 1)
11
12        # Initialize a list to store prime numbers
13        primes =  * (right + 1)
14
15        # Populate the sieve and primes list using the Sieve of Eratosthenes
16        for i in range(2, right + 1):
17            if not sieve[i]:
18                primes[prime_count] = i
19                prime_count += 1
20            j = 0
21            while primes[j] <= right // i:
22                sieve[primes[j] * i] = True
23                if i % primes[j] == 0:
24                    break
25                j += 1
26
27        # Filter primes within the given range [left, right]
28        filtered_primes = [v for v in primes[:prime_count] if left <= v <= right]
29
30        # Initialize minimum difference as infinity
31        min_difference = inf
32
33        # Initialize answer with a pair of -1 to indicate no primes found
34        closest_pair = [-1, -1]
35
36        # Iterate over each pair of subsequent primes to find the closest pair
37        for a, b in zip(filtered_primes, filtered_primes[1:]):
38            difference = b - a
39            if difference < min_difference:
40                min_difference = difference
41                closest_pair = [a, b]
42
43        # Return the closest pair of prime numbers
44        return closest_pair
45
46# The pairwise function no longer exists in Python 3, so we replace it with a zip
47# iteration over the filtered_primes and its subsequent elements. This creates pairs of primes.
48``````

## Java Solution

``````1class Solution {
2    // Function to find the two closest primes within a given range [left, right]
3    public int[] closestPrimes(int left, int right) {
4        // Counter for the number of primes found
5        int primeCount = 0;
6        // Boolean array to mark non-prime numbers (sieve)
7        boolean[] sieve = new boolean[right + 1];
8        // Array to store prime numbers
9        int[] primes = new int[right + 1];
10
11        // Sieve of Eratosthenes to find all primes up to 'right'
12        for (int i = 2; i <= right; ++i) {
13            if (!sieve[i]) {
14                // If the number is prime, add it to the list of primes
15                primes[primeCount++] = i;
16            }
17            // Mark multiples of prime[i] as non-prime
18            for (int j = 0; primes[j] <= right / i; ++j) {
19                sieve[primes[j] * i] = true;
20                // If 'i' is a multiple of prime[j], break to maintain the sieve property
21                if (i % primes[j] == 0) {
22                    break;
23                }
24            }
25        }
26
27        // Indices for tracking the closest pair of primes
28        int firstPrimeIndex = -1, secondPrimeIndex = -1;
29        // Find the range of indices for primes within [left, right]
30        for (int k = 0; k < primeCount; ++k) {
31            if (primes[k] >= left && primes[k] <= right) {
32                if (firstPrimeIndex == -1) {
33                    firstPrimeIndex = k;
34                }
35                secondPrimeIndex = k;
36            }
37        }
38
39        // Array to store the result
40        int[] result = new int[] {-1, -1};
41        // If there are not two different primes or no primes at all, return the default result
42        if (firstPrimeIndex == secondPrimeIndex || firstPrimeIndex == -1) {
43            return result;
44        }
45
46        // Initialize the minimum distance between primes to a large number
47        int minDistance = Integer.MAX_VALUE;
48        // Iterate through primes within the given range and find the closest pair
49        for (int k = firstPrimeIndex; k < secondPrimeIndex; ++k) {
50            int distance = primes[k + 1] - primes[k];
51            // Update the closest pair if a smaller distance is found
52            if (distance < minDistance) {
53                minDistance = distance;
54                result = primes[k];
55                result = primes[k + 1];
56            }
57        }
58
59        // Return the closest pair of primes
60        return result;
61    }
62}
63``````

## C++ Solution

``````1#include <vector>
2#include <cstring>
3using namespace std;
4
5class Solution {
6public:
7    // Returns the pair of closest primes between left and right (inclusive)
8    vector<int> closestPrimes(int left, int right) {
9        int primeCount = 0;
10        bool isComposite[right + 1]; // Array to mark non-primes
11        memset(isComposite, 0, sizeof isComposite); // Initialize all to false
12        vector<int> primes(right + 1); // Stores the list of primes within the range
13
14        // Sieve of Eratosthenes to generate primes up to 'right'
15        for (int i = 2; i <= right; ++i) {
16            if (!isComposite[i]) {
17                primes[primeCount++] = i; // Found a prime, add to the list
18            }
19            // Mark multiples of primes as composite numbers (non-prime)
20            for (int j = 0; primes[j] <= right / i; ++j) {
21                isComposite[primes[j] * i] = true;
22                if (i % primes[j] == 0) {
23                    break; // Optimization: break if 'i' is divisible by primes[j]
24                }
25            }
26        }
27
29        int startPrimeIndex = -1, endPrimeIndex = -1;
30
31        // Find the starting and ending index of primes within the given range [left, right]
32        for (int k = 0; k < primeCount; ++k) {
33            if (primes[k] >= left && primes[k] <= right) {
34                if (startPrimeIndex == -1) {
35                    startPrimeIndex = k; // Set the start index
36                }
37                endPrimeIndex = k; // Keep updating the end index
38            }
39        }
40
41        // Prepare the result vector with default values (-1, -1)
42        vector<int> result = {-1, -1};
43        // If there is only one or no primes within the range return the default result
44        if (startPrimeIndex == endPrimeIndex || startPrimeIndex == -1) return result;
45
46        int minDifference = INT_MAX; // Initialize minimum difference to max possible value
47
48        // Find the closest pair of primes within the given range
49        for (int k = startPrimeIndex; k < endPrimeIndex; ++k) {
50            int difference = primes[k + 1] - primes[k];
51            if (difference < minDifference) {
52                minDifference = difference; // Update the minimum difference
53                result = primes[k]; // Update the result pair
54                result = primes[k + 1];
55            }
56        }
57
58        return result;
59    }
60};
61``````

## Typescript Solution

``````1function closestPrimes(left: number, right: number): number[] {
2    let primeCount = 0;
3    // Initialize an array to mark non-primes with false
4    // using Array.prototype.fill in TypeScript
5    const isComposite: boolean[] = new Array(right + 1).fill(false);
6
7    // Array to store the list of primes within the range
8    const primes: number[] = new Array(right + 1);
9
10    // Sieve of Eratosthenes to generate primes up to 'right'
11    for (let i = 2; i <= right; ++i) {
12        if (!isComposite[i]) {
13            // Found a prime, add to the list
14            primes[primeCount++] = i;
15        }
16        // Mark multiples of primes as non-prime (composite)
17        for (let j = 0; j < primeCount && primes[j] <= right / i; ++j) {
18            isComposite[primes[j] * i] = true;
19            if (i % primes[j] === 0) {
20                // Optimization: break if 'i' is divisible by primes[j]
21                break;
22            }
23        }
24    }
25
27    let startPrimeIndex = -1, endPrimeIndex = -1;
28
29    // Find the starting and ending index of primes within the given range [left, right]
30    for (let k = 0; k < primeCount; ++k) {
31        if (primes[k] >= left && primes[k] <= right) {
32            if (startPrimeIndex === -1) {
33                // Set the start index
34                startPrimeIndex = k;
35            }
36            // Keep updating the end index
37            endPrimeIndex = k;
38        }
39    }
40
41    // Prepare the result vector with default values (-1, -1)
42    let result: number[] = [-1, -1];
43    // If there is only one or no primes within the range return the default result
44    if (startPrimeIndex === endPrimeIndex || startPrimeIndex === -1) {
45        return result;
46    }
47
48    let minDifference = Number.MAX_SAFE_INTEGER; // Initialize minimum difference to max possible value
49
50    // Find the closest pair of primes within the given range
51    for (let k = startPrimeIndex; k < endPrimeIndex; ++k) {
52        let difference = primes[k + 1] - primes[k];
53        if (difference < minDifference) {
54            // Update the minimum difference
55            minDifference = difference;
56            // Update the result pair using the current prime and the next prime
57            result = primes[k];
58            result = primes[k + 1];
59        }
60    }
61
62    return result;
63}
64``````

## Time and Space Complexity

### Time Complexity

The time complexity of the prime number generation part of the algorithm can be analyzed as follows:

• The outer loop runs from 2 to `right + 1`, which gives us a complexity of O(N), where N is the value of `right`.
• The inner loop runs up to `right // i`, this part is similar to the sieve of Eratosthenes, which has time complexity of O(N log(log N)) in the worst-case scenario.

However, we perform the inner loop operations only when we find a new prime (when `st[i]` is `False`). Besides, every number is marked at most once by its smallest prime factor in the sieve. Hence the effective number of operations would still be O(N log(log N)).

The complexity for the pairwise comparison part where the function `pairwise` is used is:

• For a list of primes, we will be doing a constant time operation for each pair of primes, which is O(P-1) = O(P), where P is the number of primes in the range `[left, right]`.

Therefore, the total time complexity combines the time complexity of the prime sieve O(N log(log N)) and the pairwise iteration O(P), resulting in a final time complexity of O(N log(log N) + P).

### Space Complexity

For space complexity, the factors include:

• A boolean sieve `st` of size `right + 1`, giving us a space complexity of O(N), where N is the value of `right`.
• An array `prime` of size `right + 1` for storing prime numbers, which also has a space complexity of O(N).
• A list `p` derived from the `prime` array, but it only contains primes within the range `[left, right]`. In the worst case scenario, this would be dense with all primes, having a complexity of O(N).

Considering all of the above, the overall space complexity is O(N) because all the arrays are of the order of size `right + 1`, and the constants are ignored in Big O notation.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫