Closest Prime Numbers in Range

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

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.

1class Solution {2    // Helper function to check for primality using trial division3    private boolean isPrime(int n) {4        if (n <= 1) {5            return false;6        }7        for (int i = 2; i * i <= n; i++) {8            if (n % i == 0) {9                return false;10            }11        }12        return true;13    }14 15    public int[] closestPrimes(int left, int right) {16        java.util.List<Integer> primes = new java.util.ArrayList<>();17        for (int i = left; i <= right; i++) {18            if (isPrime(i)) {19                primes.add(i);20            }21        }22 23        if (primes.size() < 2) {24            return new int[]{-1, -1};25        }26 27        int minDiff = Integer.MAX_VALUE;28        int[] result = new int[]{-1, -1};29 30        for (int i = 0; i < primes.size() - 1; i++) {31            int diff = primes.get(i + 1) - primes.get(i);32            if (diff < minDiff) {33                minDiff = diff;34                result[0] = primes.get(i);35                result[1] = primes.get(i + 1);36            }37        }38        return result;39    }40}

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

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.

1class Solution {2    public int[] closestPrimes(int left, int right) {3        // Step 1: Sieve of Eratosthenes to find all primes up to 'right'4        boolean[] isPrime = new boolean[right + 1];5        java.util.Arrays.fill(isPrime, true);6        isPrime[0] = isPrime[1] = false;7        for (int p = 2; p * p <= right; p++) {8            if (isPrime[p]) {9                for (int i = p * p; i <= right; i += p) {10                    isPrime[i] = false;11                }12            }13        }14 15        // Step 2: Find the closest prime pair in the range [left, right]16        int minDiff = Integer.MAX_VALUE;17        int[] result = new int[]{-1, -1};18        int prevPrime = -1;19 20        for (int i = left; i <= right; i++) {21            if (isPrime[i]) {22                if (prevPrime != -1) {23                    int diff = i - prevPrime;24                    if (diff < minDiff) {25                        minDiff = diff;26                        result[0] = prevPrime;27                        result[1] = i;28                    }29                }30                prevPrime = i;31            }32        }33        return result;34    }35}