java最大公因数最小公倍数
时间: 2023-11-04 08:54:26 浏览: 39
最大公因数可以使用两种方法来求解:方法一是通过循环遍历两个数中较大的正整数,利用取余操作判断是否能整除,最后得到最大公因数。方法二是利用辗转相除法,通过递归计算两个数的余数和较小数的最大公因数。以下是两种方法的Java实现:
方法一:
```java
public static int gcd(int a, int b) {
int max = (a > b) ? a : b;
int result = 0;
for (int i = 1; i < max; i++) {
if (a % i == 0 && b % i == 0) {
result = i;
}
}
return result;
}
```
方法二:
```java
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
int r = a % b;
return gcd(b, r);
}
```
最小公倍数可以使用两种方法来求解:方法一是传统的算法,通过找到两个数之间的最大数,逐步递增直到找到一个数同时能够整除这两个数,该数就是最小公倍数。方法二是使用公式法,通过两个数的最大公因数来计算最小公倍数。以下是两种方法的Java实现:
方法一:
```java
public static int lcm(int a, int b) {
int temp = 0;
if (a <= 0 || b == 0) {
return -1;
}
temp = Math.max(a, b);
while (temp % a != 0 || temp % b != 0) {
temp++;
}
return temp;
}
```
方法二:
```java
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
int r = a % b;
return gcd(b, r);
}
```