Java Program to Find GCD of Two Numbers

在本节中，我们介绍了在 Java 程序中查找两个数的最大公约数的不同逻辑。

最大公约数：它是能完全整除两个或更多数的最大数。它缩写为 GCD。它也称为最大公因数 (GCF) 和最高公因数 (HCF)。它用于简化分数。

如何查找最大公因数

• 写出每个数字的所有因子。
• 选择公因子。
• 选择最大的数作为 GCF。

示例：查找 12 和 8 的 GCF。

解决方案

12的因数：1, 2, 3, 4, 6, 12

8 的因子：1、2、4、8

公因数：1、2、4

最大公因数：4

因此，12 和 8 的 GCF 是 4。

查找 GCD 的算法

• 声明两个变量，例如 x 和 y。
• 对 x 和 y 运行一个从 1 到 x 和 y 的最大值的循环。
• 检查该数是否完全整除这两个数（x 和 y）。如果完全整除，则将其存储在一个变量中。
• 除以存储的数。

在 Java 中，我们可以使用以下方法查找两个数的 GCD：

• 使用 Java for 循环
• 使用 while 循环
• 使用用户自定义方法
• 使用欧几里得算法
• 使用模运算符

使用 Java for 循环

在下面的程序中，我们初始化了两个数 x=12 和 y=8。之后，我们使用了一个 for 循环，该循环从 1 运行到两个数中较小的一个。它一直执行，直到条件 i <= x && i <= y 返回 true。在 for 循环内部，我们还使用了 if 语句，该语句测试条件 (x%i==0 && y%i==0)，如果两个条件都满足，则返回 true。最后，我们将 i 的值存储在变量 gcd 中，并打印该 gcd 变量。

FindGCDExample1.java

输出

GCD of 12 and 8 is: 4

使用Java while循环

在下面的示例中，我们使用了 while 循环来测试条件。该循环一直执行，直到条件 n1!=n2 变为 false。

FindGCDExample2.java

输出

GCD of n1 and n2 is: 10

在上面的程序中，我们可以用以下逻辑替换 while 循环，得到相同的输出。

FindGCDExample3.java

输出

GCD =  4

使用用户自定义方法

在下面的程序中，我们定义了一个名为 findGCD() 的方法。它包含查找两个数 GCD 的逻辑。我们解析了两个 int 类型的参数 a 和 b。

FindGCDExample4.java

输出

Enter the First Number: 75
Enter the Second Number: 125
GCD of 75 and 125 = 25

使用欧几里得算法

欧几里得算法是一种计算两个数 GCD 的高效方法。它也称为欧几里得算法。该算法说明：

• 如果 A=0，则 GCD(A,B)=B，因为 GCD(0,B)=B，我们可以退出算法。
• 如果 B=0，则 GCD(A,B)=A，因为 GCD(A,0)=A，我们可以退出算法。
• 将 A 写入从 (A=B*Q+R) 得到的商中。

让我们通过一个Java 程序来实现上述逻辑。

FindGCDExample5.java

输出

Enter the two numbers: 
11
33
The GCD of two numbers is: 11

使用取模运算符

在下面的程序中，我们定义了一个名为 findGCD() 的递归函数。它解析两个 int 类型的参数 a 和 b。如果第二个数字 (b) 等于 0，则该方法返回 a 作为 GCD，否则返回 a%b。

FindGCDExample6.java

输出

GCD of 112 and 543 is 1

让我们看看另一个查找两个数 GCD 的逻辑。

FindGCDExample7.java

输出

GCD of 54 and 24 is 6