2523. Closest Prime Numbers in Range - Medium

前往題目

想法

• 先用昨天的Sieve of Eratosthenes找出範圍內所有質數
• 比較各質數區間就可以回傳結果

思路

1. Sieve of Eratosthenes找出範圍內所有質數
2. 比較質數區間的大小找出最小值

Code

class Solution {
    public int[] closestPrimes(int left, int right) {
        if (right - left < 1) return new int[]{-1, -1};

        boolean[] isPrime = new boolean[right + 1];

        // Default all prime
        Arrays.fill(isPrime, true);

        // Find the prime numbers
        for (int i = 2; i <= Math.sqrt(right); ++i) {
            if (isPrime[i]) {
                // Mark its multiples as "Not prime"
                for (int j = i * i; j <= right; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        List<Integer> primesInRange = new ArrayList<>();
        // Record all the primes
        for (int i = left; i <= right; ++i) {
            if (i >= 2 && isPrime[i]) {
                primesInRange.add(i);
            }
        }

        // 0 or 1 prime only
        if (primesInRange.size() < 2) return new int[]{-1, -1};

        int[] res = new int[]{-1, -1};
        int minDiff = Integer.MAX_VALUE;
        
        // Find the closest pair
        for (int i = 0; i < primesInRange.size() - 1; ++i) {
            int diff = primesInRange.get(i + 1) - primesInRange.get(i);

            if (diff < minDiff) {
                minDiff = diff;
                res[0] = primesInRange.get(i);
                res[1] = primesInRange.get(i + 1);
            }
        }

        return res;
    }
}

▶

有瑕疵的code

class Solution {
    public int[] closestPrimes(int left, int right) {
        if (right - left <= 2) return new int[]{-1, -1}; // Incorrect edge case handling. Should be `right - left < 1`.

        boolean[] isPrime = new boolean[right + 1]; // Correct.

        // Default all prime
        for (int i = 0; i < isPrime.length; ++i) {
            isPrime[i] = true; // Correct, but inefficient for large ranges. Should start from `i = 2`.
        }

        // Find the prime numbers
        for (int i = 2; i <= Math.sqrt(isPrime.length); ++i) { // Correct.
            if (isPrime[i]) {
                // Mark its multiples as "Not prime"
                for (int j = i * i; j < isPrime.length; j += i) { // Correct.
                    isPrime[j] = false; // Correct.
                }
            }
        }

        int l = left, r = left + 1; // Incorrect initialization. Should iterate through primes in the range `[left, right]`.
        int[] res = new int[]{0, 1000000}; // Incorrect initialization. Should be `{-1, -1}`.

        // Go through all the prime number pairs
        while (r < right) { // Incorrect loop condition. Should iterate through primes in the range.
            // Both prime
            if (isPrime[l] && isPrime[r]) { // Incorrect logic. `l` and `r` are not guaranteed to be primes.
                if (res[1] - res[0] > (r + left) - (l + left)) { // Incorrect difference calculation. `l` and `r` are already in the range.
                    res[0] = l + left; // Incorrect. `l` is already in the range.
                    res[1] = r + left; // Incorrect. `r` is already in the range.
                }
            } else if (!isPrime[l] && isPrime[r]) { // Incorrect logic. Should iterate through primes only.
                ++l;
                ++r;
            } else if (isPrime[l] && !isPrime[r]) { // Incorrect logic. Should iterate through primes only.
                ++r;
            } else { // Incorrect logic. Should iterate through primes only.
                ++l;
                ++r;
            }
        }

        return res; // Incorrect. May return `{0, 1000000}` if no valid pair is found.
    }
}