2523. Closest Prime Numbers in Range

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.

Learn more about Math patterns.

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.

Solution Implementation

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.

Learn more about how to find time and space complexity quickly using problem constraints.