C语言实现最大公约数与最小公倍数算法

"C语言实现最大公约数(GCD)和最小公倍数(LCM)的算法" 在编程中，计算两个整数的最大公约数（Greatest Common Divisor, GCD）和最小公倍数（Least Common Multiple, LCM）是常见的数学问题。本资源提供了使用C语言解决这个问题的代码示例。 1. 最大公约数(GCD)的计算： 最大公约数是能够同时整除两个或两个以上整数的最大的正整数。在C语言中，通常使用欧几里得算法（Euclidean Algorithm）来求解GCD。该算法基于以下原理：对于正整数a和b，若b不为0，则GCD(a, b) = GCD(b, a % b)，当b为0时，a即为GCD。 给出的C语言代码中，`gcd` 函数实现了这个算法： ```c int gcd(int n, int m) { if (m == 0) return n; return gcd(m, n % m); } ``` 这里使用了递归方式实现欧几里得算法，不断将较大的数替换为两数相除的余数，直到余数为0，此时较小的数就是GCD。 2. 最小公倍数(LCM)的计算： 最小公倍数是两个或两个以上整数共有的倍数中最小的一个。LCM可以通过两个数的乘积除以它们的最大公约数来得到，公式为：LCM(a, b) = |a * b| / GCD(a, b)。 在提供的代码中，这一计算过程在`main`函数中完成： ```c x = a * b; // 计算两数乘积 if (a < b) { t = a; a = b; b = t; } // 求GCD while (b != 0) { r = a % b; a = b; b = r; } printf("Greatest common divisor: %d\n", a); printf("Least common multiple: %d\n", x / a); // 通过GCD求LCM ``` 3. 注意事项： - 在输入处理部分，使用`scanf`读取用户输入的两个整数，确保输入值为正整数，以满足算法的要求。 - 在交换变量的值时，为了防止溢出，先将较小的值存储到临时变量`t`中，再进行交换。 - 程序只处理了正整数的情况，如果需要支持负数或零，需要对输入和计算过程做相应调整。 这段C代码展示了如何利用欧几里得算法求解最大公约数，并通过这个结果计算最小公倍数。对于学习C语言以及数值计算的初学者来说，这是一个很好的实践例子。