2761. 和等于目标值的质数对 (opens new window)

1.暴力筛质数

技巧：质数表放入静态块进行预处理计算，这部分程序执行时间不会计算。否则容易超时

class Solution {
    static int[] bitmap=new int[1000001];
    static{
        bitmap[2]=1;
        for(int i=3;i<=1e6;i+=2){
            if(check(i)){
                bitmap[i]=1;
            }
        }
    }
    public static boolean check(int a){
        for(int i=2;i<=Math.sqrt(a);i++){
            if(a%i==0) return false;
        }
        return true;
    }
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> res=new ArrayList<>();
        if(n-2>=0&&bitmap[n-2]==1) res.add(new ArrayList<Integer>(Arrays.asList(2,n-2)));       
        for(int i=3;i<=n/2;i+=2){
            if(bitmap[i]==1&&bitmap[n-i]==1) res.add(new ArrayList<Integer>(Arrays.asList(i,n-i)));
        }
        return res;
    }
}

2.线性筛

传闻是欧拉大师进行数学研究得到的负产物。核心是从小到大枚举乘数进行乘法运算，利用得到的结果筛选合数。枚举的过程中保证得到的合数不会重复，从而使算法时间复杂度达到O(n)。数的量级越大，线性筛的效果越好。实现时采用一个列表和数组，其中prime从小到大保存所有质数，np【i】：判断元素i是否为质数。

具体来说 i 作为乘数时，无论 i 为质数还是合数，另一个乘数 j 从小于 i 的质数当中挑选。如果当前 j 是 i 的最小质因子，那么筛出当前合数后退出循环。

举例如下，可以看出最小质因数保证了12只能被2筛出来，如果i=4的时候筛了12=4X3，那么后面i=6的时候12=2X6就会重复。

• i=4，最小质因子为2，筛出的合数8=2X4。
• i=5, 筛出的合数为10=2X5，15=3X5，25=5X5
• i=6，最小质因子2，筛出的合数12=2X6

为什么乘数与最小质因子相乘得到合数后就退出循环？

必要性：假设目前已知质数a<b<c<d，乘数m=axbxdxd，如果计算得到合数k1=axm=axaxbxdxd后没有退出循环，而是继续利用m往下计算新的合数k2=bxm=bx(axbxdxd)=ax(bxbxdxd)，那么我们可以发现在后面遍历乘数m'=bxbxdxd时，因为a还没有到m’的最小质因数，那么利用m'可以生成合数k3=axm'=ax(bxbxdxd)=k2。这样就会导致合数重复生成计算了两次。

充分性：实际上任何合数都可以分解为m=axbxcxd多个质数相乘，而m=ax(bxcxd)=axk这种分解方法一定是唯一的(a是m的最小质因子)。只不过在线性筛当中除了a与m存在关系之外，a与k之间也存在一定的关系——a是k的最小质因子。而这个附加条件并不会影响破坏“m的分解法一定是唯一的”。

class Solution {
    static List<Integer> prime=new ArrayList<>();
    static boolean[] np=new boolean[1000001];
    static{
        for(int i=2;i<=1000000;i++){
            if(!np[i]){
               prime.add(i);
            }
            for(int j=0;j<prime.size()&&i*prime.get(j)<=1000000;j++){
                np[i*prime.get(j)]=true;
                if(i%prime.get(j)==0) break;
            }
        }
    }
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> res=new ArrayList<>();
        if(n-2>=0&&prime.contains(n-2)) res.add(new ArrayList<Integer>(Arrays.asList(2,n-2)));       
        for(int i=3;i<=n/2;i+=2){
            if(!np[i]&&!np[n-i]) res.add(new ArrayList<Integer>(Arrays.asList(i,n-i)));
        }
        return res;
    }
}