c语言中求最大公约数
时间: 2024-06-13 21:10:00 浏览: 82
C语言中求最大公约数的方法有多种,其中辗转相除法(又名欧几里德法)是最常用的一种方法。其算法过程如下:
1. 设两数为a,b,其中a > b。
2.a/b的余数,设为r。
3. 若r=0,则b为最大公约数。
4. 若r!=0,则把b的值给a,把r的值给b,返回第2步。
以下是使用辗转相除法求两个数的最大公约数的C语言代码:
```c
#include <stdio.h>
int gcd(int a, int b) {
int r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int a, b;
printf("请输入两个正整数:");
scanf("%d %d", &a, &b);
printf("%d和%d的最大公约数为:%d\n", a, b, gcd(a, b));
return 0;
}
```
相关问题
在c语言中求最大公约数和最小公倍数
以下是两种在C语言中求最大公约数和最小公倍数的方法:
方法一:利用循环法求最大公约数和最小公倍数
```c
#include <stdio.h>
int main() {
int a, b, i, gcd, lcm;
printf("请输入两个正整数:");
scanf("%d %d", &a, &b);
// 求最大公约数
for (i = 1; i <= a && i <= b; ++i) {
if (a % i == 0 && b % i == 0) {
gcd = i;
}
}
// 求最小公倍数
lcm = a * b / gcd;
printf("%d和%d的最大公约数是%d\n", a, b, gcd);
printf("%d和%d的最小公倍数是%d\n", a, b, lcm);
return 0;
}
```
方法二:利用递归法求最大公约数和最小公倍数
```c
#include <stdio.h>
// 求最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
// 求最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int a, b, gcd_value, lcm_value;
printf("请输入两个正整数:");
scanf("%d %d", &a, &b);
gcd_value = gcd(a, b);
lcm_value = lcm(a, b);
printf("%d和%d的最大公约数是%d\n", a, b, gcd_value);
printf("%d和%d的最小公倍数是%d\n", a, b, lcm_value);
return 0;
}
```
c语言枚举求最大公约数
C言中可以使用枚举法求最大公约数。具体实现方法如下:
1. 定义两个整数a和b,输入它们的值。
2. 定义一个变量i,从1开始循环到a和b中较小的那个数。
3. 在循环中,如果a和b都能被i整除,则将i赋值给一个变量ret。
4. 循环结束后,ret的值就是a和b的最大公约数。
下面是一个使用枚举法求最大公约数的C语言程序范例:
```
#include <stdio.h>
int main() {
int a, b, i, ret = 0;
scanf("%d %d", &a, &b);
int min;
for (i = 1; i < (min = a < b ? a : b); i++) {
if (a % i == 0 && b % i == 0) ret = i;
}
printf("%d和%d的最大公约数是%d", a, b, ret);
return 0;
}
```