Java 简单求两个正整数m,n 的最大公约数。除了辗转相减法
时间: 2024-01-19 07:03:49 浏览: 39
除了辗转相减法,还可以使用更高效的欧几里得算法(辗转相除法)来求解两个正整数m和n的最大公约数。
欧几里得算法的基本思路是:如果n等于0,则m就是最大公约数;否则,用n和m除以n所得的余数来递归求解。
下面是使用Java代码实现:
```
public static int gcd(int m, int n) {
if (n == 0) {
return m;
}
return gcd(n, m % n);
}
```
调用该方法,传入两个正整数m和n,即可得到它们的最大公约数。相对于辗转相减法,欧几里得算法的效率更高,因为它的递归深度更小。
相关问题
Java 简单求两个正整数m,n 的最大公约数。
可以使用辗转相减法来求解两个正整数m和n的最大公约数,具体步骤如下:
1. 如果m小于n,则交换m和n的值,使得m大于n。
2. 用m减去n,得到差d。
3. 如果d等于n,则n就是最大公约数。
4. 如果d大于n,则用n和d的差来替换m的值,即m = d - n。
5. 如果d小于n,则用n来替换m的值,即m = n。
6. 重复步骤2到5,直到d等于n为止。
下面是使用Java代码实现:
```
public static int gcd(int m, int n) {
if (m < n) {
int temp = m;
m = n;
n = temp;
}
while (m - n != 0) {
int d = m - n;
if (d > n) {
m = d;
} else {
m = n;
n = d;
}
}
return n;
}
```
调用该方法,传入两个正整数m和n,即可得到它们的最大公约数。
c语言辗转相减法求两个正整数最大公约数
可以使用以下代码实现:
```c
#include <stdio.h>
int gcd(int a, int b) {
while (a != b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}
int main() {
int a, b;
printf("请输入两个正整数:\n");
scanf("%d %d", &a, &b);
printf("它们的最大公约数是:%d\n", gcd(a, b));
return 0;
}
```
这个程序使用辗转相减法求两个正整数的最大公约数。