力扣2523题解析：寻找最接近的质数对

一、题目解读

力扣2523题要求我们在给定区间[left, right]内找到一对最接近的质数。所谓"最接近"指的是这两个质数之间的差值最小。如果区间内质数少于两个，则返回[-1, -1]。这道题考察了质数筛选算法和区间遍历技巧，是练习数论基础和算法实现的经典题目。

二、解题思路

本题采用埃拉托斯特尼筛法（Sieve of Eratosthenes）来高效筛选出区间内的所有质数。该算法的核心思想是从小到大遍历数字，当遇到质数时，将其所有倍数标记为非质数。筛选完成后，我们收集区间内所有质数，然后遍历这些质数寻找相邻差值最小的一对。这种方法的时间复杂度为O(n log log n)，空间复杂度为O(n)，非常适合处理大规模数据。

三、解题步骤

1. 初始化质数标记数组：创建一个大小为right+1的布尔数组，初始全部设为true

2. 执行筛法：从2开始，将每个质数的倍数标记为非质数

3. 收集区间质数：遍历[left, right]区间，收集所有标记为true的数字

4. 寻找最接近对：比较相邻质数差值，记录最小差值对应的质数对

5. 处理边界情况：如果质数数量不足2个，返回[-1, -1]

四、完整代码与注释

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        // 使用埃拉托斯特尼筛法找出所有质数
        vector<bool> is_prime(right + 1, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i * i <= right; ++i) {
            if (is_prime[i]) {
                for (int j = i * i; j <= right; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        
        // 收集区间内的所有质数
        vector<int> primes;
        for (int i = max(2, left); i <= right; ++i) {
            if (is_prime[i]) {
                primes.push_back(i);
            }
        }
        
        // 寻找最小间隔的质数对
        if (primes.size() < 2) {
            return {-1, -1};
        }
        
        int min_diff = INT_MAX;
        vector<int> result;
        for (int i = 1; i < primes.size(); ++i) {
            int diff = primes[i] - primes[i-1];
            if (diff < min_diff) {
                min_diff = diff;
                result = {primes[i-1], primes[i]};
            }
        }
        
        return result;
    }
};

五、总结

本文详细解析了力扣2523题的解题思路和实现方法。通过埃拉托斯特尼筛法高效筛选质数，然后遍历比较相邻质数差值，能够优雅地解决这个问题。该算法不仅适用于编程竞赛，在密码学等领域也有广泛应用。理解并掌握这种经典算法，对提升编程能力和算法思维大有裨益。