使用欧几里得算法查找两个数字的 G.C.D 和 L.C.M 的 Java 程序
欧几里得算法是一种有效的算法,可帮助我们找到两个数字的 G.C.D 和 L.C.M。在本文中,我们将学习编写一个 Java 程序,使用欧几里得算法查找两个数字的 G.C.D 和 L.C.M。
两个数字的 G.C.D.
G.C.D,称为最大公约数,是可以精确划分两个给定数字的最大公约数。现在让我们看一个例子并计算两个数字的 G.C.D。
因数 - 在数学中,因数是可以除以给定数字的数字。
Ex - 8 可以除以 1、2、4、8。因此,1、2、4、8 都是 8 的因数。
示例
考虑数字 8 和 16
8 的因数为:1、2、4、8
16 的因数为:1、2、4、8、16
8 和 16 的公因数为 1、2、4、8。在公因数中,最大的公因数是 8。因此,8 是 8 和 16 的最大公约数。
L.C.M.两个数的最小公倍数
L.C.M,即最小公倍数,是能被两个给定数整除的最小数,即最小公倍数。
倍数 - 在数学中,倍数是能被给定数整除的数。
例 - 8,16,24, 32, ... 能被 8 整除。所以 8,16,24,32 是 8 的倍数。
示例
考虑数字:8 和 16
8 的倍数为 8,16,24, ...
16 的因数为 16,32,48, ...
能被 8 和 16 整除的公倍数为 16、32、 48等等。两个数的最小公倍数是 16。因此,16 是 8 和 16 的最小公倍数。
我们现在要实现一个程序,使用欧几里得算法来查找两个数的最小公倍数和最大公倍数,因为它是在更短时间内找到最小公倍数和最大公倍数的有效方法。
欧几里得算法的工作原理是,
"如果 a>b 且 a、b 是两个整数,则 a 和 b 的最大公倍数与 b 的最大公倍数和 a 除以 b 的余数相同"。
欧几里得算法
让我们将 a 和 b 视为两个数字
如果 b=0, 那么我们返回 a 作为这两个数字的最大公倍数数字。
否则,我们用 b 替换 a,用 a、b 的余数替换 b,然后递归调用 GCD 函数。
找到 GCD 后,我们可以找到 LCM(a, b) = (a*b) / GCD
示例
第一步是将较大的数字 (36) 除以较小的数字 (24) 并找到余数。我们可以使用模数运算符 (%) 来做到这一点。
36 % 24 = 12
余数为 12。然后,我们将较小的数字 (24) 除以余数 (12),并找到新的余数。
24 % 12 = 0
余数为 0,这意味着我们找到了 24 和 36 的最大公约数。最大公约数是最后一个非零余数,即 12。
因此,24 和 36 的最大公约数是 12。我们可以通过检查 12 是 24 和 36 的公约数,并且没有更大的数字可以整除 24 和 36 来确认这一点。
最小二乘法(24,36) = (24*36)/12 = 72。
24 和 36 的最小公倍数为 72。
算法
初始化这两个数字。
编写一个递归方法来查找数字的最大公约数。
创建自定义类对象。
使用自定义类对象从主方法调用递归方法。然后使用 G.C.D 值找到数字的 L.C.M。
示例
在此示例中,我们初始化两个数字,然后创建 GCD 类的对象,并使用 GCD 类对象调用 GCD 方法,并将这两个数字传递给该方法并获取 gcd 值并存储它。然后,我们通过将两个数字相乘并除以 gcd 值来计算 lcm。然后我们打印两个数字的和 lcm。
//Java 程序使用欧几里得算法查找两个数字的 G.C.D 和 L.C.M
import java.util.*;
class Gcd{
public int GCD(int number1, int number2) {
if (number2 == 0) {
return number1;
}
return GCD(number2, number1 % number2);
}
}
public class Main {
public static void main(String[] args) {
int number_1 = 36;
int number_2 = 24;
Gcd gcdObject = new Gcd();
int gcd = gcdObject.GCD(number_1, number_2);
System.out.println("G.C.D of "+" "+number_1+" & "+number_2 +" is: "+gcd);
int lcm = (number_1 * number_2) / gcd;
System.out.println("L.C.M of "+" "+number_1+" & "+number_2 +" is: "+lcm);
}
}
输出
G.C.D of 36 & 24 is: 12 L.C.M of 36 & 24 is: 72
因此,在本文中,我们使用 Java 编程中的 Eculid 算法计算了 tw m=numbers 的 G.C.D 和 L.C.M。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

