Closest Prime Numbers in Range

Leetcode Problem:

• Closest Prime Numbers in Range

Summary

• Find two prime numbers within a given range with the minimum difference.

Approach

• Use the Sieve of Eratosthenes algorithm to generate prime numbers, then iterate through the range to find the pair with the minimum difference.

Complexity

• O(n log log n) due to the Sieve of Eratosthenes algorithm, where n is the upper bound of the range.

Explanation

• The Sieve of Eratosthenes algorithm is used to generate prime numbers up to the given upper bound
• Then, iterate through the range to find the pair of prime numbers with the minimum difference
• If no such pair exists, return [-1, -1].

Solution Code:

class Solution {
public:
    bool isPrime[1000001] = {false};
    vector closestPrimes(int left, int right) {
        for(int i = 2; i <= right; i++){
            isPrime[i] = true;
        }
        for(int i = 2; i*i <= right; i++){
            if(!isPrime[i]){
                continue;
            }
            for(int j = i *2; j <= right; j += i){
                isPrime[j] = false;
            }
        }
        
        vector ans;
        int beforePrime = 0;
        for(int i = left; i <= right; i++){
            if(!isPrime[i]){
                continue;    
            }
            if(ans.size() < 2){
                ans.push_back(i);
                beforePrime = i;
                continue;
            }
            else{
                if((ans[1] - ans[0]) > (i - beforePrime)){
                    ans[0] = beforePrime;
                    ans[1] = i;
                }
            }
            beforePrime = i;
        }
        if(ans.size() == 2) return ans;
        return {-1, -1};
    }
};