По заданному целому числу N и целому числу G найдите все пары элемента <= N, имеющие GCD больше G

Question

Учитывая целое число N и другое целое число G, найти все пары целых чисел (i, j), такие что gcd (i, j)> G, где 0 <= i, j <= N. </p>

Самое простое решение - запустить два цикла и проверить 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);
        }
    }
}