C语言辗转相除求最大公约数
时间: 2023-05-30 07:07:58 浏览: 121
以下是C语言辗转相除法求最大公约数的代码:
```
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int a, b;
printf("请输入两个数:\n");
scanf("%d%d", &a, &b);
printf("最大公约数为:%d\n", gcd(a, b));
return 0;
}
```
解释:
- 定义一个函数`gcd`,用来求两个数的最大公约数。
- 如果b等于0,则a就是最大公约数,直接返回a。
- 如果b不等于0,则递归调用gcd函数,传入b和a%b的值。
- 在主函数中,读入两个数a和b,然后调用gcd函数求它们的最大公约数,并输出结果。
相关问题
c语言辗转相除求最大公约数
辗转相除法是求解两个整数的最大公约数的一种常见算法,也称为欧几里德算法。在C语言中,可以使用递归函数来实现辗转相除法求最大公约数。具体实现过程如下:
1. 定义一个函数gcd,接收两个整数a和b作为参数。
2. 在函数内部,判断如果b等于0,则返回a。
3. 否则,递归调用gcd函数,传入参数b和a%b,直到b等于0为止。
4. 最后返回最大公约数。
下面是使用C语言实现辗转相除法求最大公约数的代码示例:
```
#include <stdio.h>
// 辗转相除法求最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int a = 0;
int b = 0;
printf("请输入两个整数:");
scanf("%d %d", &a, &b);
int result = gcd(a, b);
printf("最大公约数为:%d", result);
return 0;
}
```
c语言 辗转相除法求最大公约数
以下是使用C语言实现辗转相除法求最大公约数的代码示例:
```c
#include <stdio.h>
// 辗转相除法求最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int a = 0;
int b = 0;
printf("请输入两个整数:");
scanf("%d %d", &a, &b);
int result = gcd(a, b);
printf("最大公约数为:%d", result);
return 0;
}
```
辗转相除法是一种用于求解两个整数的最大公约数的方法。其原理是:设a、b为两个正整数,且a>b,则a和b的最大公约数等于a除以b的余数c和b之间的最大公约数。即gcd(a,b)=gcd(b,a%b)。这个过程不断重复,直到余数为0,此时b即为a和b的最大公约数。