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].

Examples

Example 1:

1
2
3
4
5

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:

1
2
3

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 <= 10^6

Solution

Method 1 - Using Sieve of Eratosthenes

  1. Key Observations:
    • Prime numbers are greater than 1 and only divisible by 1 and themselves.
    • To minimise the difference num2 - num1, we need all prime numbers in the range [left, right] to check consecutive pairs.
  2. Steps to Solve:
    • Prime Generation (Sieve of Eratosthenes):
      • Use an efficient sieve-based approach to mark primes up to right because generating primes up to right ensures all candidates between left and right.
    • Filter primes within [left, right] from the sieve result.
    • Iterate through the filtered primes to find pairs with the minimum difference num2 - num1.
  3. Edge Case:
    • If there are fewer than 2 primes between left and right, directly return [-1, -1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public int[] closestPrimes(int left, int right) {
        // Step 1: Generate all primes up to `right` using the Sieve of Eratosthenes
        boolean[] isPrime = new boolean[right + 1];
        for (int i = 2; i <= right; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i * i <= right; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= right; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // Step 2: Filter primes within the range [left, right]
        List<Integer> primesInRange = new ArrayList<>();
        for (int i = Math.max(left, 2); i <= right; i++) {
            if (isPrime[i]) {
                primesInRange.add(i);
            }
        }
        
        // Step 3: Find the closest primes
        int[] ans = {-1, -1};
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < primesInRange.size(); i++) {
            int diff = primesInRange.get(i) - primesInRange.get(i - 1);
            if (diff < minDiff) {
                minDiff = diff;
                ans[0] = primesInRange.get(i - 1);
                ans[1] = primesInRange.get(i);
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        # Step 1: Generate all primes up to `right` using the Sieve of Eratosthenes
        is_prime = [True] * (right + 1)
        is_prime[0] = is_prime[1] = False  # 0 and 1 are not primes
        
        for i in range(2, int(right**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, right + 1, i):
                    is_prime[j] = False
        
        # Step 2: Filter primes within the range [left, right]
        primes_in_range = [i for i in range(max(left, 2), right + 1) if is_prime[i]]
        
        # Step 3: Find the closest primes
        ans = [-1, -1]
        min_diff = float('inf')
        for i in range(1, len(primes_in_range)):
            diff = primes_in_range[i] - primes_in_range[i - 1]
            if diff < min_diff:
                min_diff = diff
                ans = [primes_in_range[i - 1], primes_in_range[i]]
        
        return ans

Complexity

  • ⏰ Time complexity: O(r log log r)
    • Sieve of Eratosthenes: O(n log log n) for n = right.
    • Filtering primes within [left, right]: O(r - l) where r = right and l = left.
    • Pair iteration to find the closest primes: O(p) for p primes in range.
  • 🧺 Space complexity: O(r), as the sieve requires a space proportional to right for the boolean array.