LeetCode 题解工作台
和等于目标值的质数对
给你一个整数 n 。如果两个整数 x 和 y 满足下述条件，则认为二者形成一个质数对： 1 x + y == n x 和 y 都是质数 请你以二维有序列表的形式返回符合题目要求的所有 [x i , y i ] ，列表需要按 x i 的 非递减顺序 排序。如果不存在符合要求的质数对，则返回一个空数组。…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们先预处理出 范围内的所有质数，记录在数组 中，其中 为 `true` 表示 是一个质数。 接下来，我们在 $[2, \frac{n}{2}]$ 的范围内枚举 ，那么 $y = n - x$，如果 和 均为 `true`，那么 $(x, y)$ 是一个质数对，添加到答案中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数 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
解题思路
方法一：预处理 + 枚举
我们先预处理出 范围内的所有质数，记录在数组 中，其中 为 true 表示 是一个质数。
接下来，我们在 的范围内枚举 ，那么 ，如果 和 均为 true，那么 是一个质数对，添加到答案中。
枚举结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 是题目给定的数字。
class Solution:
def findPrimePairs(self, n: int) -> List[List[int]]:
primes = [True] * n
for i in range(2, n):
if primes[i]:
for j in range(i + i, n, i):
primes[j] = False
ans = []
for x in range(2, n // 2 + 1):
y = n - x
if primes[x] and primes[y]:
ans.append([x, y])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log log n) for the sieve and O(n) for iterating primes up to n/2. Space complexity is O(n) for storing the prime flags array. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect efficient prime computation to avoid TLE for n up to 10^6.
- question_mark
Look for correct handling of duplicates and symmetry in prime pairs.
- question_mark
Check if the candidate uses O(1) lookups for prime verification.
常见陷阱
外企场景- error
Not using a sieve and checking primes naively causing timeouts.
- error
Including duplicate pairs like [7,3] after [3,7].
- error
Failing to handle small n values where no prime pairs exist.
进阶变体
外企场景- arrow_right_alt
Return prime pairs that sum to n with the largest first element instead of sorted order.
- arrow_right_alt
Count the number of prime pairs without returning the full list.
- arrow_right_alt
Allow n to be odd and find all prime pairs including repeated elements like [5,5].