C语言求最大公约数代码，三种常用算法实例分享
1. 辗转相除法（欧几里得算法）
c
include
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int num1, num2;
printf("请输入两个整数：");
scanf("%d %d", &num1, &num2);
printf("它们的最大公约数是：%d", gcd(num1, num2));
return 0;
}
2. 斯特拉森算法（又称二进制算法）
c
include
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int main() {
int num1, num2;
printf("请输入两个整数：");
scanf("%d %d", &num1, &num2);
printf("它们的最大公约数是：%d", gcd(num1, num2));
return 0;
}
3. 最小公倍数法
c
include
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 num1, num2;
printf("请输入两个整数：");
scanf("%d %d", &num1, &num2);
printf("它们的最大公约数是：%d", gcd(num1, num2));
printf("它们的最小公倍数是：%d", lcm(num1, num2));
return 0;
}
以上三种算法中，辗转相除法是最经典的一种，其原理是不断用较小的数去除以较大的数，直到余数为0，此时的被除数即为最大公约数。斯特拉森算法则是辗转相除法的改进版，它用更高效的算法实现了同样的功能。最小公倍数法则利用了最大公约数和最小公倍数之间的关系，即两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。
需要注意的是，以上代码中的gcd函数都使用了递归实现，如果输入的数值较大，可能会导致栈溢出。在实际应用中，可以考虑使用循环实现，以避免栈溢出的问题。以上代码都没有对输入进行合法性检查，如果输入的不是整数，程序可能会出现错误。在实际应用中，需要对输入进行合法性检查，以确保程序的正确性。
