递归计算最大公因数和最小公倍数原理 JAVA
时间: 2024-10-20 07:00:58 浏览: 35
在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));
}
```
相关问题
递归求最大公约数和最小公倍数
递归求最大公约数可以使用辗转相除法,递归求解,直到余数为0时,返回被除数即为最大公约数。
代码示例:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
递归求最小公倍数可以利用最大公约数的性质,通过相乘再除以最大公约数来求解。
代码示例:
```python
def lcm(a, b):
return a * b // gcd(a, b)
```
其中,`//`表示整除运算符。
js利用递归求最大公约数 和最小公倍数
求最大公约数:
```javascript
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
```
求最小公倍数:
```javascript
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
```
阅读全文