用Java编写程序,用辗转相除法求两个整数的最大公因数
时间: 2024-09-22 11:05:28 浏览: 41
在Java中,你可以使用欧几里得算法(也称为辗转相除法或更相减损术)来计算两个整数的最大公因数(Greatest Common Divisor, GCD)。这个算法基于以下原理:两个整数a和b(假设a >= b),它们的最大公约数等于较小的数和两数之差的最大公约数。
以下是使用Java编写的简单代码实现:
```java
public class Main {
public static void main(String[] args) {
int num1 = 108; // 第一个整数
int num2 = 48; // 第二个整数
int gcd = findGCD(num1, num2);
System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);
}
// 辗转相除法求最大公约数
public static int findGCD(int a, int b) {
if (b == 0) { // 如果b为0,那么a就是最大公约数
return a;
} else { // 否则继续递归调用,用a除以b得到余数
return findGCD(b, a % b); // 注意这里交换了a和b的位置
}
}
}
```
在这个代码片段中,`findGCD`方法是一个递归函数,直到余数为0时结束递归,此时的除数就是最大公约数。如果想了解该算法的工作原理或者有其他疑问,请告诉我。
阅读全文