Problem Description

You are given two positive integers left and right that define a range [left, right]. Your task is to find two prime numbers num1 and num2 within this range that satisfy the following conditions:

1. Both numbers must be prime numbers
2. They must be within the range: left <= num1 < num2 <= right
3. The difference num2 - num1 should be as small as possible among all pairs of prime numbers in the range

If multiple pairs have the same minimum difference, return the pair with the smallest num1 value. If no such pair of prime numbers exists in the given range, return [-1, -1].

For example, if the range is [10, 19], the prime numbers in this range are [11, 13, 17, 19]. The pairs and their differences would be:

• (11, 13) with difference 2
• (11, 17) with difference 6
• (11, 19) with difference 8
• (13, 17) with difference 4
• (13, 19) with difference 6
• (17, 19) with difference 2

Since we have two pairs with the minimum difference of 2: (11, 13) and (17, 19), we choose (11, 13) because it has the smaller num1 value.

The solution uses the Sieve of Eratosthenes (specifically a linear sieve implementation) to efficiently find all prime numbers up to right, then filters those within the [left, right] range. It iterates through consecutive pairs of these primes to find the pair with the minimum difference.

Intuition

The key insight is that to find the closest pair of prime numbers, we need to examine consecutive primes in the given range. Why? Because if we have primes in sorted order like p1 < p2 < p3 < ... < pn, the minimum difference must occur between adjacent primes. If we skip any prime in between, we'll only get a larger difference.

Think about it this way: if we have three primes a < b < c, then c - a = (c - b) + (b - a), which means the difference between non-adjacent primes is always larger than at least one pair of adjacent primes.

So our strategy becomes:

1. Find all prime numbers in the range [left, right]
2. Check each pair of consecutive primes
3. Track the pair with the minimum difference

But how do we efficiently find all primes? Testing each number individually for primality would be too slow. This is where the sieve algorithm comes in - it's a clever way to find all primes up to a certain number in one go.

The sieve works by marking all multiples of each prime as composite. We start with 2 (the smallest prime), mark all its multiples as non-prime, then move to the next unmarked number (which must be prime), and repeat. This gives us all primes up to right efficiently.

Once we have all primes in our range, we simply iterate through consecutive pairs using a sliding window approach (examining pairs like (p[0], p[1]), then (p[1], p[2]), and so on), keeping track of the pair with the smallest difference. Since we traverse in ascending order, if multiple pairs have the same minimum difference, we naturally get the one with the smallest num1.

Learn more about Math patterns.

Solution Approach

The solution uses the Linear Sieve (Sieve of Euler) algorithm to find all prime numbers up to right, then searches for the closest pair within the range [left, right].

Step 1: Initialize the Sieve Data Structures

• st: A boolean array of size right + 1 to mark composite numbers (True means composite)
• prime: An array to store the prime numbers we find
• cnt: Counter to track how many primes we've found

Step 2: Linear Sieve Implementation

for i in range(2, right + 1):
    if not st[i]:
        prime[cnt] = i
        cnt += 1

• Iterate from 2 to right
• If i is not marked as composite (st[i] == False), it's a prime number
• Add it to our prime array and increment the counter

Step 3: Mark Composites

j = 0
while prime[j] <= right // i:
    st[prime[j] * i] = 1
    if i % prime[j] == 0:
        break
    j += 1

• For each number i, mark its multiples with previously found primes
• The key optimization: if i % prime[j] == 0: break ensures each composite is marked exactly once by its smallest prime factor
• This makes the algorithm run in O(n) time

Step 4: Filter Primes in Range

p = [v for v in prime[:cnt] if left <= v <= right]

• Extract only the primes that fall within [left, right] from our complete list

Step 5: Find Minimum Difference Pair

mi = inf
ans = [-1, -1]
for a, b in pairwise(p):
    if (d := b - a) < mi:
        mi = d
        ans = [a, b]

• Use pairwise() to iterate through consecutive pairs (p[i], p[i+1])
• Track the pair with minimum difference
• Since we iterate in ascending order, we automatically get the pair with smallest num1 when ties occur

Time Complexity: O(n) for the linear sieve where n = right, plus O(k) for finding the minimum difference where k is the number of primes in the range

Space Complexity: O(n) for the sieve arrays

The linear sieve is more efficient than the standard Sieve of Eratosthenes because it ensures each composite number is visited only once, achieving true linear time complexity.

Example Walkthrough

Let's walk through the solution with a small example: finding the closest prime pair in the range [10, 19].

Step 1: Initialize Sieve Data Structures

• Create st array of size 20 (indices 0-19), all initialized to False
• Create prime array to store primes
• Set cnt = 0

Step 2-3: Run Linear Sieve from 2 to 19

When i = 2:

• st[2] = False, so 2 is prime
• Add to prime array: prime[0] = 2, cnt = 1
• Mark multiples: st[4] = True, st[6] = True, st[8] = True, st[10] = True, st[12] = True, st[14] = True, st[16] = True, st[18] = True

When i = 3:

• st[3] = False, so 3 is prime
• Add to prime array: prime[1] = 3, cnt = 2
• Mark multiples: st[9] = True, st[15] = True

When i = 5:

• st[5] = False, so 5 is prime
• Add to prime array: prime[2] = 5, cnt = 3
• Mark multiples: (none new in our range)

When i = 7:

• st[7] = False, so 7 is prime
• Add to prime array: prime[3] = 7, cnt = 4

When i = 11:

• st[11] = False, so 11 is prime
• Add to prime array: prime[4] = 11, cnt = 5

When i = 13:

• st[13] = False, so 13 is prime
• Add to prime array: prime[5] = 13, cnt = 6

When i = 17:

• st[17] = False, so 17 is prime
• Add to prime array: prime[6] = 17, cnt = 7

When i = 19:

• st[19] = False, so 19 is prime
• Add to prime array: prime[7] = 19, cnt = 8

All primes found: [2, 3, 5, 7, 11, 13, 17, 19]

Step 4: Filter Primes in Range [10, 19]

• Check each prime: 2 (❌), 3 (❌), 5 (❌), 7 (❌), 11 (✓), 13 (✓), 17 (✓), 19 (✓)
• Filtered list p = [11, 13, 17, 19]

Step 5: Find Minimum Difference Pair

Use pairwise iteration through consecutive primes:

• Pair (11, 13): difference = 13 - 11 = 2
  • Update: mi = 2, ans = [11, 13]
• Pair (13, 17): difference = 17 - 13 = 4
  • 4 > 2, no update
• Pair (17, 19): difference = 19 - 17 = 2
  • 2 = 2, but we keep the first occurrence (smallest num1)

Result: [11, 13] with minimum difference of 2

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n = right. This is achieved through the linear sieve algorithm (Euler's sieve) used to find all prime numbers up to right. The outer loop iterates from 2 to right, and the inner while loop ensures that each composite number is marked exactly once by its smallest prime factor, resulting in a total of O(n) operations. The subsequent filtering of primes within the range [left, right] and finding the closest pair both take O(n) time in the worst case.

The space complexity is O(n), where n = right. The algorithm uses two arrays: st (a boolean array of size right + 1) to mark composite numbers, and prime (an array of size right + 1) to store the prime numbers found. Additionally, the list p stores the filtered primes within the range, which in the worst case could be O(n) primes. Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Sieve Array Initialization

A common mistake is initializing the sieve array with size right instead of right + 1, which causes an index out of bounds error when accessing is_composite[right].

Incorrect:

is_composite = [False] * right  # Wrong! Missing the last element

Correct:

is_composite = [False] * (right + 1)  # Includes index 'right'

2. Incorrect Loop Condition in Composite Marking

The condition primes_list[j] <= right // i prevents integer overflow, but developers often write it incorrectly as primes_list[j] * i <= right, which can cause overflow issues for large values.

Problematic:

while j < prime_count and primes_list[j] * i <= right:  # May overflow

Better:

while j < prime_count and primes_list[j] <= right // i:  # Prevents overflow

3. Forgetting to Handle Edge Cases

The code must handle cases where there are fewer than 2 primes in the range. Without proper checking, pairwise() on a list with 0 or 1 elements won't produce any pairs, leaving the result as [-1, -1].

Solution: The current implementation handles this correctly by initializing result = [-1, -1] and only updating it when valid pairs are found.

4. Using Regular Sieve Instead of Linear Sieve

While both work, using the standard Sieve of Eratosthenes can be less efficient:

Less Efficient (Regular Sieve):

for i in range(2, int(right**0.5) + 1):
    if not is_composite[i]:
        for j in range(i * i, right + 1, i):
            is_composite[j] = True

More Efficient (Linear Sieve): The provided solution ensures each composite is marked exactly once.

5. Incorrect Prime Range Filtering

A subtle bug occurs when filtering primes for the range - using < instead of <= for boundaries.

Wrong:

primes_in_range = [p for p in primes_list[:prime_count] if left < p < right]

Correct:

primes_in_range = [p for p in primes_list[:prime_count] if left <= p <= right]

6. Not Breaking Ties Correctly

When multiple pairs have the same minimum difference, the problem requires returning the pair with the smallest num1. Since the primes are already sorted, iterating from smallest to largest and updating only when finding a strictly smaller difference naturally handles this requirement.