2523. Closest Prime Numbers in Range

MediumMathNumber Theory
Leetcode Link

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 = [0] * (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[0] = primes[k];
55                result[1] = 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
28        // Initialize index variables to -1 (indicating not found)
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[0] = primes[k]; // Update the result pair
54                result[1] = 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
26    // Initialize index variables to -1 (indicating not found)
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[0] = primes[k];
58            result[1] = 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 👨‍🏫