递归计算最大公因数和最小公倍数原理 JAVA
时间: 2024-10-20 07:00:58 浏览: 26
在Java中,递归可以用来计算两个数的最大公因数(GCD,Greatest Common Divisor)和最小公倍数(LCM,Least Common Multiple)。这里简单解释一下原理:
**最大公因数(GCD)递归算法**:
1. 如果两个数中有一个为0,则另一个数就是它们的最大公因数。
2. 否则,如果a大于b,那么a除以b的余数c就是新的a和b继续相除时的较小的那个数,即gcd(a, b) = gcd(b, c)。
3. 递归调用这个函数,直到余数为0,此时的b就是最大公因数。
**Java代码示例**:
```java
public static int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
```
**最小公倍数(LCM)的计算**:
1. LCM可以通过公式计算:LCM(a, b) = |a * b| / GCD(a, b),因为两数乘积等于两数的最大公约数和他们的最小公倍数的乘积。
2. 先求出GCD,然后用两数乘积除以GCD即可得到LCM。
**Java代码示例**:
```java
public static int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
```
相关问题
递归求最大公约数和最小公倍数
递归求最大公约数和最小公倍数的程序可以写成如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def lcm(a, b):
return a * b // gcd(a, b)
```
其中,`gcd()` 函数使用了辗转相除法求最大公约数,`lcm()` 函数则通过最大公约数求出最小公倍数。
调用示例:
```python
a = 24
b = 60
print("最大公约数:", gcd(a, b))
print("最小公倍数:", lcm(a, b))
```
输出结果:
```
最大公约数: 12
最小公倍数: 120
```
python中用递归找最大公约数和最小公倍数
可以使用递归函数来找最大公约数和最小公倍数。以下是示例代码:
```python
# 递归函数找最大公约数
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# 递归函数找最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
```
使用示例:
```python
a = 24
b = 36
print("最大公约数:", gcd(a, b))
print("最小公倍数:", lcm(a, b))
```
输出结果:
```
最大公约数: 12
最小公倍数: 72
```
阅读全文