在C语言中,求两个正整数的最大公约数(GCD)和最小公倍数(LCM)有多种方法。以下是几种常见的方法:
方法一:辗转相除法(欧几里得算法)
辗转相除法是求最大公约数的经典算法,其基本思想是用较大数除以较小数,再用出现的余数去除除数,如此反复,直到余数为0为止。最小公倍数可以通过两数乘积除以最大公约数得到。
```c
include
// 求最大公约数
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 求最小公倍数
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
int main() {
int a, b;
printf("请输入两个整数: ");
scanf("%d %d", &a, &b);
printf("最大公约数是: %d\n", gcd(a, b));
printf("最小公倍数是: %d\n", lcm(a, b));
return 0;
}
```
方法二:辗转相减法
辗转相减法是另一种求最大公约数的方法,通过不断将较大数减去较小数,直到两数相等为止。
```c
include
// 求最大公约数
int gcd(int a, int b) {
if (a < b) {
return gcd(b, a);
}
while (a != b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}
// 求最小公倍数
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
int main() {
int a, b;
printf("请输入两个整数: ");
scanf("%d %d", &a, &b);
printf("最大公约数是: %d\n", gcd(a, b));
printf("最小公倍数是: %d\n", lcm(a, b));
return 0;
}
```
方法三:使用全局变量
可以将最大公约数和最小公倍数设为全局变量,在主函数中输出它们的值。
```c
include
int gcd, lcm;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
gcd = a;
return gcd;
}
int lcm(int a, int b) {
lcm = (a * b) / gcd;
return lcm;
}
int main() {
int a, b;
printf("请输入两个整数: ");
scanf("%d %d", &a, &b);
gcd(a, b);
lcm(a, b);
printf("最大公约数是: %d\n", gcd);
printf("最小公倍数是: %d\n", lcm);
return 0;
}
```
方法四:输入参数
可以直接在`main`函数中通过输入参数来求最大公约数和最小公倍数。
```c
include
// 求最大公约数
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 求最小公倍数
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
int main() {
int a, b;
printf("请输入两个整数: ");
scanf("%d %d", &a, &b);
printf("最大公约数是: %d\n", gcd(a, b));
printf("最小公倍数是: %d\n", lcm(a, b));
return 0;
}
```