Путаница с внутренним и внешним циклом Java?

Question

У меня есть функция isEvenSubset(12, 18), которая возвращает 1, если все четные множители 18 лежат в четных коэффициентах 12. Эта функция возвращает 1 для 12 и 18.

18 = 2,6 (четные факторы) 12 = 2,4,6 (четные коэффициенты)

Мой код для этого приведен ниже:

public static void main(String[] args) {

    System.out.println(isEvenSubset(12, 18));
}

static int isEvenSubset(int m, int n) {
    int a=0;
    int factn=0;
    for (int i = 1; i <n; i++) {


        int factm=0;
        for (int j = 1; j <m; j++) {
            if(n%i==0&&i%2==0&&factm!=0){
                factn=i;
                System.out.println(factn+" "+factm);
                if(factn==factm){
                    a=1;
                }
                }
            if(m%j==0&&j%2==0){
            factm=j;                
            }                       
        }           
    }
    return a;
}

Результат не такой, как ожидалось. Я запутался, где в коде я должен проверить factn==factm. Может кто-нибудь дать мне подсказку, подходит ли здесь использование внутреннего и внешнего цикла, или я должен искать какой-либо другой подход.

Answer 1

Вам вообще не нужен вложенный цикл, и вы слишком усложняете простую вещь. Вы хотите знать, являются ли все четные факторы числа n подмножеством четных факторов другого числа m. Подойдите к этому так:

1. Пройдите все четные числа (2, 4, 6, 8, 10, ...) до m.
2. Проверьте, можно ли разделить ваш n.
   1. Если да, проверьте, не может ли m делиться на него. Если это так, верните false.

И все готово. Это простой трехшаговый алгоритм. В коде это может выглядеть так:

for (int f = 2; f < m; f += 2)
{
    if (n % f == 0 && m % f != 0)
    {
        return false;
    }
}
return true;

Это определенно не полностью оптимизированная версия и, вероятно, даже не близко к ней. Есть еще более простые решения для решения вашей проблемы. Однако это все еще намного сложнее, чем вы пытались.

Answer 2

Вы путаете себя, потому что ваш алгоритм слишком сложен.

Просто зациклите все четные числа от 0 до первого числа (здесь 18). Для каждого проверьте, делит ли он первое число (18). Если это так, проверьте, делит ли он также второе число (12). Если тот, который делит первое, не делит второе, выйдите и верните 0 (или false). Если вы достигнете конца цикла, все четные делители первого числа также делят второе число, поэтому верните 1 (или true).

static int isEvenSubset(int firstNumber, int secondNumber) {
    for (int i=2; i<firstNumber; i+=2) {
        if(firstNumber%i == 0) {
           if(secondNumber%i !=0) {
               return false;
           }
        }
    }
    return true;
}

Answer 3

Ваш алгоритм имеет O (n ^ 2) временную сложность, что очень плохо.

Я бы сделал функцию, которая вычисляет четные множители числа и возвращает их в массиве.

Так что ваш main должен дважды вызывать эту функцию, возвращая два массива. Затем вы должны проверить, содержатся ли все числа массива m в n. Эта временная сложность будет O (n).