难度: Medium
给你一个整数 n 。如果两个整数 x 和 y 满足下述条件，则认为二者形成一个质数对：
1 <= x <= y <= nx + y == nx 和 y 都是质数请你以二维有序列表的形式返回符合题目要求的所有 [xi, yi] ，列表需要按 xi 的 非递减顺序 排序。如果不存在符合要求的质数对，则返回一个空数组。
注意：质数是大于 1 的自然数，并且只有两个因子，即它本身和 1 。
示例 1：
输入：n = 10 输出：[[3,7],[5,5]] 解释：在这个例子中，存在满足条件的两个质数对。 这两个质数对分别是 [3,7] 和 [5,5]，按照题面描述中的方式排序后返回。
示例 2：
输入：n = 2 输出：[] 解释：可以证明不存在和为 2 的质数对，所以返回一个空数组。
提示：
1 <= n <= 106运行时间: 269 ms
内存: 30.1 MB
MX = 10 ** 6 + 1
primes = []
is_prime = [True] * MX
for i in range(2, MX):
if is_prime[i]:
primes.append(i)
for j in range(i * i, MX, i):
is_prime[j] = False
class Solution:
def findPrimePairs(self, n: int) -> List[List[int]]:
if n % 2:
return [[2, n - 2]] if n > 4 and is_prime[n - 2] else []
ans = []
for x in primes:
y = n - x
if y < x:
break
if is_prime[y]:
ans.append([x, y])
return ans
题解首先使用一个线性筛法来预先计算所有小于等于 1000000 的质数，并储存这些质数及其质数状态。在 findPrimePairs 方法中，如果 n 是奇数，则直接检查 n-2 是否为质数，因为除了 (2, n-2) 之外不可能有其他质数对和为奇数。如果 n 是偶数，题解通过遍历已知的质数列表来寻找所有可能的质数对 (x, n-x)，并保证 x <= y = n-x。这是通过检查 y 是否为质数并且 y >= x 来实现的。
时间复杂度: O(n \log \log n)
空间复杂度: O(n)
MX = 10 ** 6 + 1 # 定义最大数值范围
primes = [] # 用于存储所有质数
is_prime = [True] * MX # 布尔数组，标记是否为质数
for i in range(2, MX): # 使用线性筛法生成质数
if is_prime[i]: # 如果当前数是质数
primes.append(i) # 添加到质数列表
for j in range(i * i, MX, i): # 标记所有的倍数为非质数
is_prime[j] = False
class Solution:
def findPrimePairs(self, n: int) -> List[List[int]]:
if n % 2: # 如果 n 是奇数
return [[2, n - 2]] if n > 4 and is_prime[n - 2] else [] # 返回 (2, n-2) 若它们都是质数
ans = [] # 存储结果的列表
for x in primes: # 遍历所有质数
y = n - x # 计算配对质数
if y < x: # 如果 y 小于 x，停止循环
break
if is_prime[y]: # 检查 y 是否为质数
ans.append([x, y]) # 添加质数对到结果列表
return ans # 返回结果
在处理奇数n的情况下，因为质数除了2以外都是奇数，所以两个奇数质数相加永远是偶数，无法满足和为奇数的条件。因此，唯一可能的质数对组合就是2（唯一的偶数质数）和n-2。如果n-2也是质数，那么(2, n-2)就是符合条件的质数对。
在线性筛法中，从i的平方开始标记非质数是因为小于i的平方的倍数已经被之前的质数标记过了。例如，当i=3时，3*2（6）已经在i=2时被标记，因此从3*3（9）开始标记可以避免重复操作，提高筛法的效率。
这种策略不会漏掉任何质数对。因为在寻找质数对(x, y)时，只需要考虑x <= y的情况。一旦y小于x，意味着这对质数已经被之前的循环以(y, x)的形式检查过。因此，此策略确保每对质数对只被计算一次，避免重复。
线性筛法相比埃拉托斯特尼的筛法在效率上更高，尤其是在处理大规模数据时。线性筛法能够确保每个合数只被其最小的质因数筛选一次，从而减少了重复的操作和计算量。这使得线性筛法在时间复杂度上表现更优，尤其适用于需要快速处理高达百万级别的数据的场景。