Java программа для поиска greatest common divisor (GCD) двух чисел

Java полный список примеров

В данном примере вы узнаете, как в программе на Java найти greatest common divisor (GCD) двух чисел. Это достигается с помощью циклов for и while с помощью оператора if else.

Наибольший общий делитель (HCF) или greatest common divisor (GCD) двух целых чисел - это наибольший целое число, которое может точно делить оба числа (без остатка).

Пример 1: использование цикла for и оператора if для поиска greatest common divisor (GCD) двух чисел

public class GCD {
　　　　public static void main(String[] args) {
　　　　　　　　int n1 = 81, n2 = 153, gcd = 1;
　　　　　　　　for(int i = 1; i <= n1 && i <= n2; ++i)
　　　　　　　　{
　　　　　　　　　　　　// Проверка, является ли i делителем обоих целых чисел
　　　　　　　　　　　　if(n1 % i == 0 && n2 % i == 0)
　　　　　　　　　　　　　　　　gcd = i;
　　　　　　　　}
　　　　　　　　System.out.printf("%d и %d наибольший общий делитель (%d)", n1, n2, gcd);
　　　　}
}

При выполнении этого программы, вывод будет:

Наибольший общий делитель 81 и 153 равен 9

В данном случае, два числа, для которых нужно найти наибольший общий делитель, хранятся в n1 и n2.

Затем выполните цикл for, пока i меньше n1 и n2. Таким образом, итерируйте от 1 до наименьшего из двух чисел, чтобы найти наибольший общий делитель.

Если n1 и n2 делятся на i без остатка, то gcd устанавливается в значение числа. Продолжайте до тех пор, пока не найдете наибольшее число (GCD), которое делит n1 и n2 без остатка.

Мы также можем решить эту проблему с помощью цикла while, как показано ниже:

Пример 2: использование цикла while и оператора if else для поиска greatest common divisor (GCD) двух чисел

public class GCD {
　　　　public static void main(String[] args) {
　　　　　　　　int n1 = 81, n2 = 153;
　　　　　　　　while(n1 != n2)
　　　　　　　　{
　　　　　　　　　　　　if(n1 > n2)
　　　　　　　　　　　　　　　　n1 -= n2;
　　　　　　　　　　　　else
　　　　　　　　　　　　　　　　n2 -= n1;
　　　　　　　　}
　　　　　　　　System.out.println("G.C.D = " + n1);
　　　　}
}

При выполнении этого программы, вывод будет:

G.C.D = 9

Это лучший способ найти GCD. В этом методе вы subtract larger integer from smaller integer and then assign the result to the variable that stores the larger integer. Этот процесс продолжается до тех пор, пока n1 и n2 не станут равны.

Только когда пользователь вводит положительное целое число, вышеуказанные два программы могут работать по ожидаемому плану. Вот некоторые изменения во втором примере, чтобы найти GCD положительных и отрицательных чисел.

Пример 3: положительные и отрицательные числа как GCD

public class GCD {
　　　　public static void main(String[] args) {
　　　　　　　　int n1 = 81, n2 = -153;
　　　　　　　　n1 = (n1 > 0) ? n1 : -n1;
　　　　　　　　n2 = (n2 > 0) ? n2 : -n2;
　　　　　　　　while(n1 != n2)
　　　　　　　　{
　　　　　　　　　　　　if(n1 > n2)
　　　　　　　　　　　　　　　　n1 -= n2;
　　　　　　　　　　　　else
　　　　　　　　　　　　　　　　n2 -= n1;
　　　　　　　　}
　　　　　　　　System.out.println("G.C.D = " + n1);
　　　　}
}

При выполнении этого программы, вывод будет:

G.C.D = 9

Java полный список примеров