用Java编写程序,用辗转相除法求两个整数的最大公约数
时间: 2024-09-22 11:05:22 浏览: 53
输入两个正整数m和n,求其最大公因数和最小公倍数
在Java中,我们可以使用欧几里得算法(也称为辗转相除法或更相减损术)来计算两个整数的最大公约数(Greatest Common Divisor, GCD)。这个算法基于这样一个原理:对于任意两个正整数a和b,它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
以下是使用Java编写的简单代码来实现辗转相除法:
```java
public class GCD {
public static int gcd(int num1, int num2) {
if (num2 == 0) {
return num1;
} else {
// 使用递归调用
return gcd(num2, num1 % num2);
}
}
public static void main(String[] args) {
int a = 60; // 第一个整数
int b = 48; // 第二个整数
System.out.println("The greatest common divisor of " + a + " and " + b + " is: " + gcd(a, b));
}
}
```
在这个例子中,`gcd`方法接受两个参数,如果第二个参数为零,那么返回第一个参数,因为任何数和零的最大公约数都是那个非零的数。否则,我们递归地调用`gcd`,传入第二个参数和第一个参数除以第二个参数的余数,直到找到余数为零的情况。
阅读全文