Java编写用辗转相除法求最大公约数和最小公倍数。
时间: 2024-10-19 18:08:33 浏览: 13
在Java中,我们可以使用欧几里得算法(也称为辗转相除法)来计算两个整数的最大公约数(Greatest Common Divisor, GCD)。然后,根据数论知识,两个数a和b的最小公倍数(Least Common Multiple, LCM)可以用公式 `LCM(a, b) = |a * b| / GCD(a, b)` 来计算。
以下是使用递归实现辗转相除法求GCD的Java代码示例:
```java
public class EuclideanAlgorithm {
public static int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
public static void main(String[] args) {
int num1 = 48;
int num2 = 18;
System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd(num1, num2));
// 计算最小公倍数
int lcm = Math.abs(num1 * num2) / gcd(num1, num2);
System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm);
}
}
```
在这个例子中,`gcd` 函数会一直调用自身,直到找到两个数的最大公约数。在`main`函数中,我们先计算了给定数值的最大公约数,然后利用上面提到的公式计算出最小公倍数。
阅读全文