给定一个中间体 N 和一个整数 G，找到 GCD 大于 G 的所有元素对 <=N

Question

给定一个整数 N 和另一个整数 G，找到所有整数对 （i，j），使得 gcd （i，j）> G 其中 0<=i，j<=N。

最简单的解决方案是运行两个循环并检查每对的 gcd，这将导致 O（n^2） 复杂性。

我想到的第二种方法是运行从 G+1 到 N/2 的循环，对于每个 i，获取其所有倍数。但这不会生成所有货币对。

        List<Pair<Integer, Integer>> ll = new LinkedList<>();
        for(int i=g+1;i<=n/2;i++){
            List<Integer> l = new LinkedList<>();
            for(int j=i+i;j<=n;j+=i){
                ll.add(new Pair<>(i, j));
            }
        }

第三种方法是考虑从G+1到N的所有元素，并且对于每个元素，它们的所有除数>G。

        List<Pair<Integer, Integer>> ll = new LinkedList<>();
        for(int j=g+1;j<=n;j++) {
            for (int i = g+1; i <= Math.sqrt(j); i++) {
                if (i != j && j % i == 0 && (j/i)!= j) {
                    if (j / i == i && i>g) // check if divisors are equal
                        ll.add(new Pair<>(i, j));
                    else {
                        if(i > g) ll.add(new Pair<>(i, j));
                        if (j / i > g) ll.add(new Pair<>(j / i, j));
                    }
                }
            }
        }

我正在寻找更优化的解决方案。请帮忙。

Answer 1

你可以用这个算法来生成你的对：从 G+1 开始，对于每个整数直到 N/2，创建一个小于 N 的乘数列表。例如，如果 G=3 和 N=19，你将从：

• 4： 4， 8， 12， 16
• 5： 5， 10， 15
• 6： 6， 12， 18
• 7： 7， 14
• 8： 8， 16
• 9： 9， 18

您需要通过选择任何配对（不包括双打）从此列表中进行配对：4：8、4：12、4：16、8：12、8：16、12：16、5：

10、5：15、10：15、6：12、6：18、12：18、7：14、9：18。你可以一次做一组乘数，从 G+1 到 N/2。此代码的复杂度为 O（（N/2-G）*K），其中 K 是乘数列表的长度，最多为 N/（G+1）。您可以通过跳过已经出现在乘数列表中的数字来进一步改善这一点（例如，在我们的示例中，我们不需要处理 8）。

生成它的代码很简单：

int n = 1000;
int g = 1;
boolean[] skipMultiplier = new boolean[n+1];
Set<Pair<Integer,Integer>> pairs = new HashSet<Pair<Integer,Integer>>();
for (int i=g+1; i<n/2+1 ;i++) {
    List<Integer> multipliers = new ArrayList<Integer>();
    for (int j=2; j< n/i+1 ; j++) {
        if (skipMultiplier[i]) {
            continue;
        }
        multipliers.add(i*j);
        skipMultiplier[i*j] = true;
        Pair<Integer,Integer> pair = new Pair<Integer,Integer>(i,i*j);
        pairs.add(pair);
    }
    for (int j=0; j<multipliers.size()-1; j++) {
        for (int k=j+1; k<multipliers.size(); k++) {
            Pair<Integer,Integer> pair = 
                new Pair<Integer,Integer> (multipliers.get(j), multipliers.get(k));
            pairs.add(pair);
        }
    }
}