java实现辗转相除法
时间: 2023-10-25 14:10:11 浏览: 89
好的,Java实现辗转相除法的代码如下:
```
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
```
该函数接收两个参数a和b,返回它们的最大公约数。辗转相除法是求最大公约数的一种常见算法,通过反复用较小数去除较大数的余数来实现。
相关问题
java实现辗转相除法(附完整源码)
以下是Java实现辗转相除法的完整源码:
```java
import java.util.Scanner;
public class EuclideanAlgorithm {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取两个数
System.out.print("请输入第一个数:");
int a = scanner.nextInt();
System.out.print("请输入第二个数:");
int b = scanner.nextInt();
// 计算最大公约数
int gcd = gcd(a, b);
// 输出结果
System.out.println("最大公约数为:" + gcd);
scanner.close();
}
/**
* 辗转相除法计算最大公约数
*
* @param a 第一个数
* @param b 第二个数
* @return 最大公约数
*/
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
}
```
使用时,只需在主函数中调用 `gcd` 方法即可。
java中辗转相除法
辗转相除法,也称欧几里得算法,是一种求最大公约数的算法。在Java中,可以使用以下代码实现辗转相除法:
```
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
```
其中,a和b是要求最大公约数的两个数,%是取模运算符,表示a除以b的余数。这个算法的时间复杂度为O(log n),其中n是a和b中较小的那个数的位数。
辗转相除法在Java中的应用非常广泛,例如求两个数的最大公约数、判断两个数是否互质等等。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)