# Closest Prime Numbers in Range
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/closest-prime-numbers-in-range)
Canonical: https://scaleengineer.com/dsa/problems/closest-prime-numbers-in-range
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
---
## Problem
Given two positive integers `left` and `right`, find the two integers `num1` and `num2` such that:

* `left <= num1 < num2 <= 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 <= left <= right <= 106`

# Approaches
## Brute-Force with Trial Division
This approach involves iterating through every number in the given range `[left, right]`. For each number, we perform a primality test. The numbers that are identified as prime are stored in a list. Finally, we iterate through the list of found primes to find the pair with the minimum difference.
**Time:** O((right - left) * sqrt(right)). For each number in the range of size `N = right - left + 1`, we perform a primality test that takes up to `O(sqrt(right))` time. This is too slow for the given constraints. · **Space:** O(P), where P is the number of primes in the range `[left, right]`. In the worst case, this is approximately `O((right-left)/log(right))`. The space is used to store the list of prime numbers.
**Pros:** Conceptually simple and easy to implement.; Requires minimal extra space, only for storing the primes found in the range.
**Cons:** The time complexity is very high, making it impractical for the given constraints (`right` up to 10^6).; It will likely result in a 'Time Limit Exceeded' error on most online judges.
### Explanation
The core of this method is a helper function, `isPrime(n)`, which determines if a number `n` is prime. This is done using trial division: we check if `n` is divisible by any integer from 2 up to its square root. If a divisor is found, `n` is not prime.

The main logic first builds a list of all prime numbers within `[left, right]` by calling `isPrime()` on each number. Once this list is populated, if it contains fewer than two primes, no such pair exists, and we return `[-1, -1]`. Otherwise, we iterate through the sorted list of primes, comparing each adjacent pair `(p1, p2)` and keeping track of the pair with the smallest difference `p2 - p1`. The first pair found with the minimum difference is the answer, as the list is sorted, satisfying the tie-breaking rule.

```java
class Solution {
    // Helper function to check for primality using trial division
    private boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public int[] closestPrimes(int left, int right) {
        java.util.List<Integer> primes = new java.util.ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (isPrime(i)) {
                primes.add(i);
            }
        }

        if (primes.size() < 2) {
            return new int[]{-1, -1};
        }

        int minDiff = Integer.MAX_VALUE;
        int[] result = new int[]{-1, -1};

        for (int i = 0; i < primes.size() - 1; i++) {
            int diff = primes.get(i + 1) - primes.get(i);
            if (diff < minDiff) {
                minDiff = diff;
                result[0] = primes.get(i);
                result[1] = primes.get(i + 1);
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a helper function `isPrime(n)` that checks if a number `n` is prime using trial division. This involves checking for divisibility by numbers from 2 up to `sqrt(n)`.
- Initialize an empty list, `primesInRange`, to store the prime numbers found.
- Iterate through each number `i` from `left` to `right`.
- If `isPrime(i)` returns true, add `i` to the `primesInRange` list.
- After the loop, check if `primesInRange` contains at least two numbers. If not, return `[-1, -1]` as no valid pair exists.
- Initialize `minDiff` to infinity and an answer array `ans` to `[-1, -1]`.
- Iterate through the `primesInRange` list from the first to the second-to-last element.
- For each adjacent pair of primes `(p1, p2)`, calculate the difference `diff = p2 - p1`.
- If `diff` is less than `minDiff`, update `minDiff` to `diff` and `ans` to `[p1, p2]`.
- After checking all adjacent pairs, return the `ans` array.

## Sieve of Eratosthenes
A much more efficient approach is to pre-compute all prime numbers up to `right` using the Sieve of Eratosthenes. This avoids the costly primality test for each number in the range. After sieving, we can iterate through the range `[left, right]` once to find the closest prime pair.
**Time:** O(right * log(log(right))). The Sieve of Eratosthenes runs in `O(right * log(log(right)))` time. The subsequent pass over the range `[left, right]` takes `O(right - left)` time. The overall complexity is dominated by the sieve. · **Space:** O(right). A boolean array of size `right + 1` is required to store the primality information for all numbers up to `right`.
**Pros:** Highly efficient and the standard method for prime-related problems within this range.; The time complexity is nearly linear, making it very fast for the given constraints.
**Cons:** Requires O(right) auxiliary space, which could be a concern if `right` were significantly larger (e.g., > 10^7).
### Explanation
First, we create a boolean array, say `isPrime`, of size `right + 1`, and initialize all values to `true`, assuming all numbers are prime initially. We then apply the Sieve of Eratosthenes algorithm. We mark 0 and 1 as not prime. Then, we iterate from `p = 2` up to `sqrt(right)`. If `p` is still marked as prime, we iterate through its multiples (starting from `p*p`) and mark them as not prime.

After the sieve is complete, the `isPrime` array accurately tells us which numbers are prime. We then iterate from `left` to `right`. We keep track of the most recently seen prime number, `prevPrime`. When we encounter a new prime `i`, we check if `prevPrime` has been set. If it has, we calculate the difference `i - prevPrime` and compare it with our current minimum difference, updating the result if we find a smaller gap. This single pass through the range is sufficient to find the required pair.

```java
class Solution {
    public int[] closestPrimes(int left, int right) {
        // Step 1: Sieve of Eratosthenes to find all primes up to 'right'
        boolean[] isPrime = new boolean[right + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= right; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= right; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // Step 2: Find the closest prime pair in the range [left, right]
        int minDiff = Integer.MAX_VALUE;
        int[] result = new int[]{-1, -1};
        int prevPrime = -1;

        for (int i = left; i <= right; i++) {
            if (isPrime[i]) {
                if (prevPrime != -1) {
                    int diff = i - prevPrime;
                    if (diff < minDiff) {
                        minDiff = diff;
                        result[0] = prevPrime;
                        result[1] = i;
                    }
                }
                prevPrime = i;
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a boolean array `isPrime` of size `right + 1` and initialize all entries from 2 to `right` as `true`.
- Mark `isPrime[0]` and `isPrime[1]` as `false`.
- Apply the Sieve of Eratosthenes algorithm: Iterate from `p = 2` up to `sqrt(right)`. If `p` is prime (i.e., `isPrime[p]` is `true`), mark all its multiples (starting from `p*p`) as not prime by setting `isPrime[j] = false`.
- After the sieve is complete, initialize `minDiff` to infinity, `ans = [-1, -1]`, and `prevPrime = -1`.
- Iterate through the numbers `i` from `left` to `right`.
- If `isPrime[i]` is `true`:
  - Check if `prevPrime` has been set (i.e., `prevPrime != -1`).
  - If it has, calculate the difference `diff = i - prevPrime`.
  - If `diff` is smaller than `minDiff`, update `minDiff` to `diff` and set `ans` to `[prevPrime, i]`.
  - Update `prevPrime` to the current prime `i`.
- Return the `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] closestPrimes(int left, int right) {
    int cnt = 0;
    boolean[] st = new boolean[right + 1];
    int[] prime = new int[right + 1];
    for (int i = 2; i <= right; ++i) {
      if (!st[i]) {
        prime[cnt++] = i;
      }
      for (int j = 0; prime[j] <= right / i; ++j) {
        st[prime[j] * i] = true;
        if (i % prime[j] == 0) {
          break;
        }
      }
    }
    int i = -1, j = -1;
    for (int k = 0; k < cnt; ++k) {
      if (prime[k] >= left && prime[k] <= right) {
        if (i == -1) {
          i = k;
        }
        j = k;
      }
    }
    int[] ans = new int[]{-1, -1};
    if (i == j || i == -1) {
      return ans;
    }
    int mi = 1 << 30;
    for (int k = i; k < j; ++k) {
      int d = prime[k + 1] - prime[k];
      if (d < mi) {
        mi = d;
        ans[0] = prime[k];
        ans[1] = prime[k + 1];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> closestPrimes(int left, int right) {
    int cnt = 0;
    bool st[right + 1];
    memset(st, 0, sizeof st);
    int prime[right + 1];
    for (int i = 2; i <= right; ++i) {
      if (!st[i]) {
        prime[cnt++] = i;
      }
      for (int j = 0; prime[j] <= right / i; ++j) {
        st[prime[j] * i] = true;
        if (i % prime[j] == 0) {
          break;
        }
      }
    }
    int i = -1, j = -1;
    for (int k = 0; k < cnt; ++k) {
      if (prime[k] >= left && prime[k] <= right) {
        if (i == -1) {
          i = k;
        }
        j = k;
      }
    }
    vector<int> ans = {-1, -1};
    if (i == j || i == -1)
      return ans;
    int mi = 1 << 30;
    for (int k = i; k < j; ++k) {
      int d = prime[k + 1] - prime[k];
      if (d < mi) {
        mi = d;
        ans[0] = prime[k];
        ans[1] = prime[k + 1];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]: cnt = 0 st = [False] * (right + 1) prime = [0] * (right + 1) for i in range(2, right + 1): if not st[i]: prime[cnt] = i cnt += 1 j = 0 while prime[j] <= right // i: st[prime[j] * i] = 1 if i % prime[j] == 0: break j += 1 p = [v for v in prime[: cnt] if left <= v <= right] mi = inf ans = [- 1, - 1] for a, b in pairwise(p): if (d: = b - a) < mi: mi = d ans = [a, b] return ans

```