НОД двух чисел в Java — программа через цикл while

Наибольший общий делитель (НОД, англ. GCD) двух чисел — это самое большое число, на которое оба числа делятся без остатка. Например, НОД(81, 153) = 9.

Пример 1: НОД с помощью цикла for и if

Самый прямолинейный способ: пробежать все числа от 1 до меньшего из чисел и запомнить наибольшее из тех, на которое делятся оба числа.

class Main {
  public static void main(String[] args) {

    // find GCD between n1 and n2
    int n1 = 81, n2 = 153;

    // initially set to gcd
    int gcd = 1;

    for (int i = 1; i <= n1 && i <= n2; ++i) {

      // check if i perfectly divides both n1 and n2
      if (n1 % i == 0 && n2 % i == 0)
        gcd = i;
    }

    System.out.println("GCD of " + n1 +" and " + n2 + " is " + gcd);
  }
}

Вывод:

GCD of 81 and 153 is 9

Цикл for идёт по всем числам от 1 до меньшего из n1 и n2. Если i делит оба числа без остатка, значение gcd обновляется. В итоге в gcd остаётся самое большое из подходящих чисел.

Пример 2: НОД с помощью цикла while и if/else (алгоритм вычитания)

Более быстрый и красивый способ — алгоритм Евклида через вычитание: из большего числа вычитаем меньшее, пока числа не сравняются.

class Main {
  public static void main(String[] args) {

    // find GCD between n1 and n2
    int n1 = 81, n2 = 153;

    while(n1 != n2) {

      if(n1 > n2) {
        n1 -= n2;
      }

      else {
        n2 -= n1;
      }
    }

    System.out.println("GCD: " + n1);
  }
}

Вывод:

GCD: 9

Это более эффективный способ найти НОД. Из большего числа вычитается меньшее и результат сохраняется на месте большего. Процесс продолжается, пока n1 и n2 не станут равны.

Предупреждение

Обе версии выше работают корректно только для положительных чисел. Чтобы поддержать и отрицательные, нужно сначала привести числа к их модулю.

Пример 3: НОД для положительных и отрицательных чисел

Перед основным алгоритмом приведём числа к положительному виду с помощью тернарного оператора.

class GCD {
  public static void main(String[] args) {

    int n1 = 81, n2 = -153;

    // Always set to positive
    n1 = ( n1 > 0) ? n1 : -n1;
    n2 = ( n2 > 0) ? n2 : -n2;

    while(n1 != n2) {

      if(n1 > n2) {
        n1 -= n2;
      }

      else {
        n2 -= n1;
      }
    }

    System.out.println("GCD: " + n1);
  }
}

Вывод:

GCD: 9