Prime Pairs With Target Sum 和等于目标值的质数对

问题描述：

给你一个整数 n 。如果两个整数 x 和 y 满足下述条件，则认为二者形成一个质数对：

1 <= x <= y <= n
x + y == n
x 和 y 都是质数
请你以二维有序列表的形式返回符合题目要求的所有 $x_i, y_i]$ ，列表需要按 xi 的非递减顺序排序。如果不存在符合要求的质数对，则返回一个空数组。

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

$1<=n<=10^6$

分析

问题本身不复杂，就是要在1~n的范围内找到x,y,并且加和为 $n$ 。

如果不考虑其他的条件，整个问题就是two sum的变形。
但是额外的要求就是 $x <= y$ ,并且是质数

质数的定义，就是只能被1和它自己整除。

所以策略就是从 $1\rightarrow n$ ，枚举 $x$ ，从而得到 $y = n - x$ ,同时需要判断 $x$ 和 $y$ 是质数。

Risk

如果使用最简单的暴力枚举判断x是否为质数，那么它的时间复杂度就是 $O(\sqrt{N})$ ,而 $x$ 的最少要枚举到 $n /2$ 。以问题的最大规模 $n=10^6$ ,一共要判断 $n$ 次质数，时间复杂度为 $O(N*\sqrt{N})$ ，整体的规模大概是 $10^9$ 。

所以需要其他更优秀的方法来完成质数的验证。

比如素数筛，埃氏筛或者欧拉筛。

这2个筛都可以在接近 $O (N)$ 的时间复杂度内，完成对 $1\rightarrow ~n$ 中所有质数标记。

所以使用线性的时间复杂度，完成质数的标记。然后再以线性时间复杂度完成X的枚举，整体时间复杂度 $O (N)$ ，几乎完美。

但是素数筛，自身是需要 $O (N)$ 的空间，即 $10^6$ .

代码

	private boolean[] flag;
    private long _n; 
    private void init(){// 埃氏筛
        flag = new boolean[(int)_n];
        for (long i = 2; i < flag.length; i++) {
            if (!flag[(int)i]) {		  
                if((long)(i*i)>_n) continue;
			    for (long j = i*i; j < flag.length; j+= i) {
					flag[(int)j] = true;
				}
			}
        }
    } 
	public List<List<Integer>> findPrimePairs(int n) {	
        ArrayList<List<Integer>> list = new ArrayList<>();
        _n = n;
        init();
		for (int i = 2; i <= n / 2; i++) {          
			if (!flag[i] &&!flag[n-i]){
				list.add(List.of(i, n - i));
			}
		}
		return list;
	}