Medium

题目描述

给你两个正整数 left 和 right，请你找到两个整数 num1 和 num2，使得：

  • left <= num1 < num2 <= right
  • num1 和 num2 都是质数
  • num2 - num1 是满足上述条件的所有其他对中最小的

返回正整数数组 ans = [num1, num2]。如果有多个满足条件的数对，返回 num1 最小的那个。如果不存在这样的数字，返回 [-1, -1]。

示例 1：

输入：left = 10, right = 19
输出：[11,13]
解释：10 到 19 之间的质数有 11、13、17 和 19。
任意两个质数之间最近的间距是 2，可以由 [11,13] 或 [17,19] 实现。
由于 11 小于 17，我们返回第一个数对。

示例 2：

输入：left = 4, right = 6
输出：[-1,-1]
解释：给定范围内只有一个质数，因此无法满足条件。

提示：

  • 1 <= left <= right <= 10^6

解题思路

这道题要求在给定区间内找到间距最小的两个质数。我们可以分为两个步骤来解决：

  1. 使用埃拉托斯特尼筛法找出所有质数：由于 right 最大为 10^6，我们需要高效地判断数字是否为质数。埃拉托斯特尼筛法可以在 O(n log log n) 时间内筛出所有小于等于 n 的质数。

  2. 遍历区间内的质数找最小间距：将区间 [left, right] 内的所有质数收集起来，然后遍历相邻的质数对，找到间距最小的一对。如果有多个相同的最小间距，选择第一个质数较小的那对。

具体实现时，我们先用筛法标记所有质数，然后从 left 开始遍历，收集所有质数到一个列表中。最后遍历这个列表，找到相邻质数间的最小差值。

时间复杂度主要由筛法决定，为 O(right log log right)，空间复杂度为 O(right)。

推荐解法：使用埃拉托斯特尼筛法 + 一次遍历的方法，既高效又简洁。

代码实现

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        // 埃拉托斯特尼筛法
        vector<bool> isPrime(right + 1, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= right; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= right; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // 收集区间内的质数
        vector<int> primes;
        for (int i = left; i <= right; i++) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
        }
        
        // 如果质数少于2个，返回[-1,-1]
        if (primes.size() < 2) {
            return {-1, -1};
        }
        
        // 找最小间距的质数对
        int minDiff = INT_MAX;
        vector<int> result = {-1, -1};
        
        for (int i = 1; i < primes.size(); i++) {
            int diff = primes[i] - primes[i-1];
            if (diff < minDiff) {
                minDiff = diff;
                result = {primes[i-1], primes[i]};
            }
        }
        
        return result;
    }
};

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        # 埃拉托斯特尼筛法
        is_prime = [True] * (right + 1)
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(right**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, right + 1, i):
                    is_prime[j] = False
        
        # 收集区间内的质数
        primes = []
        for i in range(left, right + 1):
            if is_prime[i]:
                primes.append(i)
        
        # 如果质数少于2个，返回[-1,-1]
        if len(primes) < 2:
            return [-1, -1]
        
        # 找最小间距的质数对
        min_diff = float('inf')
        result = [-1, -1]
        
        for i in range(1, len(primes)):
            diff = primes[i] - primes[i-1]
            if diff < min_diff:
                min_diff = diff
                result = [primes[i-1], primes[i]]
        
        return result

public class Solution {
    public int[] ClosestPrimes(int left, int right) {
        // 埃拉托斯特尼筛法
        bool[] isPrime = new bool[right + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= right; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= right; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // 收集区间内的质数
        List<int> primes = new List<int>();
        for (int i = left; i <= right; i++) {
            if (isPrime[i]) {
                primes.Add(i);
            }
        }
        
        // 如果质数少于2个，返回[-1,-1]
        if (primes.Count < 2) {
            return new int[] {-1, -1};
        }
        
        // 找最小间距的质数对
        int minDiff = int.MaxValue;
        int[] result = {-1, -1};
        
        for (int i = 1; i < primes.Count; i++) {
            int diff = primes[i] - primes[i-1];
            if (diff < minDiff) {
                minDiff = diff;
                result = new int[] {primes[i-1], primes[i]};
            }
        }
        
        return result;
    }
}

var closestPrimes = function(left, right) {
    // 埃拉托斯特尼筛法
    const isPrime = new Array(right + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    for (let i = 2; i * i <= right; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= right; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 收集区间内的质数
    const primes = [];
    for (let i = left; i <= right; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }
    
    // 如果质数少于2个，返回[-1,-1]
    if (primes.length < 2) {
        return [-1, -1];
    }
    
    // 找最小间距的质数对
    let minDiff = Infinity;
    let result = [-1, -1];
    
    for (let i = 1; i < primes.length; i++) {
        const diff = primes[i] - primes[i-1];
        if (diff < minDiff) {
            minDiff = diff;
            result = [primes[i-1], primes[i]];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(right log log right)埃拉托斯特尼筛法的时间复杂度
空间复杂度O(right)需要 right+1 大小的布尔数组存储质数标记

相关题目