#2523

Medium

LeetCode Problem Workspace

Closest Prime Numbers in Range

Find the two closest prime numbers within a given range using efficient number theory techniques and gap comparisons.

Problem Statement

Given two positive integers left and right, identify two integers num1 and num2 such that both are prime, left <= num1 < num2 <= right, and their difference is minimized.

Return the array [num1, num2]. If multiple pairs share the same minimal difference, select the one with the smaller num1. If no valid pair exists, return [-1, -1]. For example, left = 10 and right = 19 yields [11,13].

Examples

Example 1

Input: left = 10, right = 19

Output: [11,13]

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]

There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints

1 <= left <= right <= 106

Solution Approach

Generate Primes Using Sieve

Use the Sieve of Eratosthenes to mark all primes up to right. This creates a fast lookup for each number's primality and avoids repeated prime checks.

Track Closest Pair

Iterate through the primes within the range. Maintain the previous prime and update the minimal gap whenever a closer pair is found. This ensures the pair with the smallest num1 is returned if gaps are equal.

Handle Edge Cases

If fewer than two primes exist in the range, return [-1, -1]. This accounts for ranges with one prime or no primes and avoids invalid array outputs.

Complexity Analysis

Metric	Value
Time	O(\min(1452, R - L) \cdot sqrt(R))
Space	O(1)

Time complexity is O(min(1452, right-left) * sqrt(right)) due to prime checking using the Sieve. Space complexity is O(1) beyond the prime markers, since only previous prime and minimal gap need tracking.

What Interviewers Usually Probe

Expect optimized prime generation rather than naive primality checks.
Look for minimal gap handling to ensure correct pair selection.
Check edge cases where the range has fewer than two primes.

Common Pitfalls or Variants

Common pitfalls

Not handling single-prime or empty ranges and returning invalid pairs.
Failing to track the previous prime correctly, causing incorrect minimal gap results.
Assuming consecutive numbers are primes instead of iterating through the sieve results.

Follow-up variants

Find the farthest prime numbers in a given range instead of the closest.
Return all prime pairs with the same minimal gap within a range.
Compute the closest prime pair in a very large range efficiently using segmented sieve.

FAQ

What is the recommended method to find primes efficiently in this problem?

Use the Sieve of Eratosthenes to mark all primes up to right, enabling fast lookups and minimal gap computation.

How do I handle ranges with fewer than two primes?

Return [-1, -1] since no valid pair can exist in these cases.

Does the problem Closest Prime Numbers in Range require checking every number individually?

No, iterating only over primes generated by the sieve avoids unnecessary checks and improves performance.

What if multiple prime pairs have the same minimal difference?

Select the pair with the smaller first prime num1 according to the problem requirement.

What is the time complexity pattern for this number theory problem?

Generating primes up to right using a sieve gives roughly O(min(1452, right-left) * sqrt(right)), optimized over naive primality tests.

terminal

Solution

Solution 1: Linear Sieve

For the given range $[\textit{left}, \textit{right}]$, we can use the linear sieve method to find all prime numbers. Then, we traverse the prime numbers in ascending order to find the pair of adjacent prime numbers with the smallest difference, which will be the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Continue Practicing

#2521 distinct prime factors of product of array #2513 minimize the maximum of two arrays #2507 smallest value after replacing with sum of prime factors