Problem Informations

• Problem Index: 2523
• Problem Link: Closest Prime Numbers in Range
• Topics: Math, Number Theory

Problem Description

Given two positive integers left and right, find the two integers num1 and num2 such that:

• $left \leq num1 < num2 \leq right$.
• Both num1 and num2 are 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 smallest num1 value. If no such numbers exist, return $[-1, -1]$.

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 \leq left \leq right \leq 10^6$

Intuition

The problem requires finding two prime numbers within a given range such that the difference between them is minimized. This suggests iterating through the numbers in the range and checking each number for primality. To achieve the minimum difference, once two consecutive prime numbers are identified, they should be compared to any existing closest pair recorded to determine if they are closer.

Approach

The fundamental approach to solving this problem involves iterating from the left boundary to the right boundary, checking each number for primality, and then maintaining a record of the two closest prime numbers found. The detailed steps are as follows:

1. Prime Check Function:

   • A helper function, is_prime, is used to determine if a number is prime.
   • It handles edge cases by returning false for numbers less than 2 and true for 2 and 3 directly.
   • For numbers greater than 3, it eliminates even numbers and multiples of 3 immediately to reduce unnecessary computations.
   • For all other numbers, it checks divisibility starting from 5 up to the square root of the number, incrementing by 6, because numbers 5 and 7 are the first non-multiples after skipping multiples of smaller primes (2 and 3).

2. Iterating Over the Range:

   • Initialize a variable previousPrime to store the last identified prime and result to store the closest pair of primes found. Initially, both are set to indicate no valid primes found (-1).

3. Identify Closest Primes:

   • Loop through each integer from left to right.
   • For each integer, use the is_prime function to determine if it is a prime number.
   • If a prime number is found, check if it can form a closer pair with the previousPrime than any pair previously recorded in result by comparing the differences.
   • If a closer pair is found, update result with the new pair of primes.
   • Update previousPrime to the current prime number.

4. Return Result:

   • After completing the iteration, return the result which contains the pair of closest primes or [-1, -1] if no valid pair was found.

This approach ensures that the solution is efficient and respects the constraints by minimizing operations on non-prime numbers and only focusing on potential prime candidates. Additionally, it ensures the smallest num1 is prioritized by updating results only when necessary.

Code

C++

class Solution {
public:
    // Check if a number is prime
    bool is_prime(int n) {
        if (n < 2) return false; // Numbers less than 2 are not prime
        if (n == 2 || n == 3) return true; // 2 and 3 are prime numbers
        if (n % 2 == 0 || n % 3 == 0) return false; // Eliminate multiples of 2 and 3

        // Check for factors of n starting from 5
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }

    // Find the closest prime numbers between left and right
    vector<int> closestPrimes(int left, int right) {
        int previousPrime = -1; // Stores the last found prime number
        vector<int> result = {-1, -1}; // Stores the pair of closest primes

        for (int i = left; i <= right; i++) {
            if (is_prime(i)) {
                // Check if the current prime and the previous prime are closer than the current result
                if (previousPrime != -1 && (result[0] == -1 || i - previousPrime < result[1] - result[0])) {
                    result = {previousPrime, i}; // Update the result with the new closest pair
                }
                previousPrime = i; // Update the previous prime to the current prime
            }
        }
        
        return result;
    }
};

Python

class Solution:
    # Check if a number is prime
    def is_prime(self, n: int) -> bool:
        if n < 2:
            return False  # Numbers less than 2 are not prime
        if n == 2 or n == 3:
            return True  # 2 and 3 are prime numbers
        if n % 2 == 0 or n % 3 == 0:
            return False  # Eliminate multiples of 2 and 3

        # Check for factors of n starting from 5
        for i in range(5, int(n**0.5) + 1, 6):
            if n % i == 0 or n % (i + 2) == 0:
                return False
        return True

    # Find the closest prime numbers between left and right
    def closestPrimes(self, left: int, right: int) -> list[int]:
        previousPrime = -1  # Stores the last found prime number
        result = [-1, -1]  # Stores the pair of closest primes

        for i in range(left, right + 1):
            if self.is_prime(i):
                # Check if the current prime and the previous prime are closer than the current result
                if previousPrime != -1 and (result[0] == -1 or i - previousPrime < result[1] - result[0]):
                    result = [previousPrime, i]  # Update the result with the new closest pair
                previousPrime = i  # Update the previous prime to the current prime

        return result

Complexity

• Time complexity: The overall time complexity is $O(n \sqrt{m})$, where $n$ is the difference between right and left ($n = \text{right} - \text{left} + 1$), and $m$ is the maximum number within the range, which is essentially right. The reason is that for each number between left and right, the is_prime function is called, which has a time complexity of $O(\sqrt{m})$ due to checking possible divisors up to the square root of the number.

• Space complexity: The space complexity is $O(1)$. The algorithm uses a constant amount of space for variables like previousPrime and result, and no additional space is required that scales with the input size.