Medium

题目描述

给你一个整数 n。如果两个整数 x 和 y 满足以下条件，我们就说它们组成一个质数对：

  • 1 <= x <= y <= n
  • x + y == n
  • x 和 y 都是质数

返回以 [xi, yi] 形式表示的质数对的二维数组，并按 xi 的递增顺序排序。如果不存在质数对，则返回一个空数组。

注意：质数是指大于 1 且只有两个因子（1 和它本身）的自然数。

示例 1：

输入：n = 10
输出：[[3,7],[5,5]]
解释：在这个例子中，有两个满足条件的质数对。
这些对是 [3,7] 和 [5,5]，我们按照题目要求以排序的顺序返回它们。

示例 2：

输入：n = 2
输出：[]
解释：可以证明不存在和为 2 的质数对，所以我们返回一个空数组。

约束条件：

  • 1 <= n <= 10^6

解题思路

解题思路

这道题要求找到所有和为 n 的质数对 [x, y]，其中 x <= y。

核心思路：

  1. 预处理质数：由于 n 最大可达 10^6，我们需要高效地判断数字是否为质数。使用埃拉托色尼筛法预处理出所有小于等于 n 的质数，时间复杂度 O(n log log n)。

  2. 枚举较小的数：对于每个可能的 x（从 2 到 n/2），检查 x 和 n-x 是否都是质数。由于要求 x <= y，我们只需要枚举到 n/2 即可避免重复。

  3. 优化判断：通过预处理的质数表，可以在 O(1) 时间内判断一个数是否为质数。

算法步骤：

  1. 使用埃拉托色尼筛法生成质数表
  2. 遍历 x 从 2 到 n/2
  3. 如果 x 和 n-x 都是质数，则添加到结果中
  4. 由于按 x 递增顺序遍历，结果天然有序

这种方法避免了对每个数都进行质数判断的低效操作，是处理大规模数据的最优解法。

代码实现

class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        // 使用埃拉托色尼筛法预处理质数
        vector<bool> isPrime(n + 1, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        vector<vector<int>> result;
        // 枚举较小的数 x，确保 x <= y
        for (int x = 2; x <= n / 2; x++) {
            int y = n - x;
            if (isPrime[x] && isPrime[y]) {
                result.push_back({x, y});
            }
        }
        
        return result;
    }
};

class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        # 使用埃拉托色尼筛法预处理质数
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        
        i = 2
        while i * i <= n:
            if is_prime[i]:
                j = i * i
                while j <= n:
                    is_prime[j] = False
                    j += i
            i += 1
        
        result = []
        # 枚举较小的数 x，确保 x <= y
        for x in range(2, n // 2 + 1):
            y = n - x
            if is_prime[x] and is_prime[y]:
                result.append([x, y])
        
        return result

public class Solution {
    public IList<IList<int>> FindPrimePairs(int n) {
        // 使用埃拉托色尼筛法预处理质数
        bool[] isPrime = new bool[n + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        IList<IList<int>> result = new List<IList<int>>();
        // 枚举较小的数 x，确保 x <= y
        for (int x = 2; x <= n / 2; x++) {
            int y = n - x;
            if (isPrime[x] && isPrime[y]) {
                result.Add(new List<int> {x, y});
            }
        }
        
        return result;
    }
}

var findPrimePairs = function(n) {
    // 使用埃拉托色尼筛法预处理质数
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    const result = [];
    // 枚举较小的数 x，确保 x <= y
    for (let x = 2; x <= Math.floor(n / 2); x++) {
        const y = n - x;
        if (isPrime[x] && isPrime[y]) {
            result.push([x, y]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log log n + n/2) = O(n log log n)，其中埃拉托色尼筛法为 O(n log log n)，枚举质数对为 O(n/2)
空间复杂度O(n)，主要用于存储质数筛数组

相关题目