Closest Prime Numbers in Range

Closest Prime Numbers in Range

What is this problem about?

The Closest Prime Numbers in Range interview question asks you to find two prime numbers within a given closed interval [left, right] such that their absolute difference is minimized. If there are multiple pairs with the same minimum difference, you should return the pair with the smallest left value. If fewer than two prime numbers exist in the range, you return [-1, -1].

Why is this asked in interviews?

Companies like Microsoft and Google ask the Closest Prime Numbers in Range coding problem to test your knowledge of Number Theory and efficient searching. Generating prime numbers efficiently is a fundamental computer science task. This problem specifically evaluates whether you can use a sieve method (like Sieve of Eratosthenes) to handle large ranges without exceeding time or memory limits.

Algorithmic pattern used

The most efficient Math interview pattern for this problem is the Sieve of Eratosthenes. Instead of checking each number for primality individually (which is slow for large ranges), you create a boolean array up to right and mark non-primes. Once you have the list of primes between left and right, finding the "closest" pair is a simple linear scan through the sorted primes.

Example explanation

Range: [10, 20]

1. Use a sieve to find all primes up to 20: 2, 3, 5, 7, 11, 13, 17, 19.
2. Filter primes that are >= 10: 11, 13, 17, 19.
3. Check adjacent differences:
   • |13 - 11| = 2
   • |17 - 13| = 4
   • |19 - 17| = 2
4. Both [11, 13] and [17, 19] have a difference of 2.
5. Return the one with the smaller first element: [11, 13].

Common mistakes candidates make

• Inefficient Primality Check: Using a naive O(sqrt(N)) primality test for every number in the range, which can be too slow if the range is large (e.g., 10^6 numbers).
• Ignoring the "Smallest" Rule: Forgetting to return the first pair encountered when differences are tied.
• Handling 1: Forgetting that 1 is not a prime number.

Interview preparation tip

Always remember that the Sieve of Eratosthenes takes O(N log log N) time, which is nearly linear. It is almost always the preferred way to find multiple primes in a range.