用java写一个求两个数最大公因数的算法
时间: 2023-05-17 07:06:27 浏览: 74
以下是一个用 Java 编写的求两个数最大公因数的算法:
```java
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
```
这个算法使用了递归来求解两个数的最大公因数。如果第二个数为 0,则第一个数就是最大公因数;否则,将第二个数和第一个数模第二个数的余数作为新的两个数,继续递归求解。
相关问题
java两个数最大公约数_java 求两个数的最大公约数
好的,我知道了。对于求两个数的最大公约数,可以使用欧几里得算法(辗转相除法),具体步骤如下:
1. 用较小的数除以较大的数,如果余数为0,则较大的数就是最大公约数;
2. 如果余数不为0,则用较大的数除以余数,再用余数去除上一步的余数,直到余数为0;
3. 当余数为0时,上一步的除数就是最大公约数。
下面是Java代码实现:
```java
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
```
其中,a和b分别为要求最大公约数的两个数,如果其中一个数为0,则返回另一个数。否则,递归调用gcd函数,将b和a%b作为参数传入,直到b为0,返回a即为最大公约数。
用java 求两个数的最大公约数和最小公倍数
最大公约数和最小公倍数可以使用辗转相除法(也称欧几里得算法)来求解。
最大公约数的算法:
```java
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
```
最小公倍数的算法:
```java
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
```
其中,gcd(a, b)表示a和b的最大公约数,lcm(a, b)表示a和b的最小公倍数。
完整代码如下:
```java
public class GcdLcmDemo {
public static void main(String[] args) {
int a = 12, b = 18;
int gcd = gcd(a, b);
int lcm = lcm(a, b);
System.out.println("最大公约数:" + gcd);
System.out.println("最小公倍数:" + lcm);
}
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
}
```