给你一个整数 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 <= 106

WA的原因：需要在类外进行数据的预处理

比赛ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        def f(x):
            if (x == 2) or (x == 3):
                return True
            if (x % 6 != 1) and (x % 6 != 5):
                return False
            for i in range(5, int(x ** 0.5) + 1, 6):
                if (x % i == 0) or (x % (i + 2) == 0):
                    return False
            return True

        # n = 3
        # se = set([i for i in range(2,n) if f(i)])
        ans = []
        for l in range(2,n):
            r = n - l
            if l == 2 or ( l%2==1 and r%2==1):
                if l <= r  and f(l) and f(r):
                    ans.append([l,r])
        return ans

灵神代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 预处理
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