和等于目标值的质数对
难度:
标签:
题目描述
You are given an integer n. We say that two integers x and y form a prime number pair if:
1 <= x <= y <= nx + y == nxandyare prime numbers
Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.
Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.
Example 1:
Input: n = 10 Output: [[3,7],[5,5]] Explanation: In this example, there are two prime pairs that satisfy the criteria. These pairs are [3,7] and [5,5], and we return them in the sorted order as described in the problem statement.
Example 2:
Input: n = 2 Output: [] Explanation: We can show that there is no prime number pair that gives a sum of 2, so we return an empty array.
Constraints:
1 <= n <= 106
代码结果
运行时间: 269 ms, 内存: 30.1 MB
/*
* 思路：
* 1. 通过流生成从2到n的所有质数。
* 2. 然后，利用流检查所有可能的质数对(x, y)，满足x + y == n。
* 3. 最后，返回所有满足条件的质数对，并按x的非递减顺序排序。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class PrimePairsStream {
// 方法：判断一个数是否是质数
public static boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
public static List<int[]> findPrimePairs(int n) {
return IntStream.rangeClosed(2, n / 2)
.filter(x -> isPrime(x) && isPrime(n - x))
.mapToObj(x -> new int[]{x, n - x})
.collect(Collectors.toList());
}
public static void main(String[] args) {
int n = 10;
List<int[]> primePairs = findPrimePairs(n);
primePairs.forEach(pair -> System.out.println(Arrays.toString(pair)));
}
}
解释
方法:
题解首先使用一个线性筛法来预先计算所有小于等于 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)
代码细节讲解
🦆
为什么在处理奇数n的情况下，题解中只考虑了配对(2, n-2)，而没有考虑其他可能的质数配对？
▷🦆
在使用线性筛法预计算质数时，为什么需要从i的平方开始标记非质数，而不是从2i开始？
▷🦆
题解中提到如果y小于x就停止循环，这种策略是否会漏掉某些质数对？
▷🦆
题解采用了线性筛法而不是其他筛法（例如埃拉托斯特尼的筛法），这是基于什么考虑？
▷