C语言求最大公约数及最小公倍数.pdf

最大公约数和最小公倍1. 最⼤公约数 1.1 定义 最⼤公约数（Greatest Common Divisor，GCD），也称最⼤公因数、最⼤公因⼦，是⼀种数学概念，指两个或多个整数共有约数中最 ⼤的⼀个。 1.2 解法⼀：常规法（暴⼒法） 1.2.1 定义 由于最⼤公约数的本质是⼀个最⼤的能同时被两整数整除的⾃然数。所以我们先⽐较两数⼤⼩，从较⼤数开始向上递增，直到找到那个最⼩ 公倍数 在C语言中，求最大公约数（Greatest Common Divisor, GCD）和最小公倍数（Least Common Multiple, LCM）是常见的算法问题，主要应用于数论和计算机科学领域。本文将详细介绍几种不同的方法来解决这个问题。 1. **最大公约数**： - **定义**：最大公约数是两个或多个整数共有的约数中最大的一个。它反映了这些数之间的共同因子程度。 - **解法一：常规法（暴力法）**：通过从较大的数开始向上递增，检查每个数是否能同时被两个整数整除。例如，代码中的`gcd4`函数通过循环遍历，找到符合条件的公约数。 - **解法二：辗转相除法（欧几里得法）**：这是利用两个数相除的余数来逐步缩小范围的方法。每次用较大的数除以较小的数，然后用余数代替原较小的数，重复此过程直到余数为零，最后的除数即为GCD。递归和非递归两种实现方式在`gcd1`和`gcd2`函数中都有体现。 - **解法三：更相减损法**：通过不断用较大数减去较小数，直到两个数相等，这个相等的数就是最大公约数。在实际编程中，需要考虑偶数的情况，可能需要先进行约简。 2. **最小公倍数**： - 最小公倍数（LCM）是能够同时被两个或多个整数整除的最小正整数。在C语言中，可以通过以下公式计算两个数的LCM：`LCM(a, b) = |a * b| / GCD(a, b)`，其中`|a * b|`表示a和b的乘积的绝对值。 3. **代码实现**： - 对于最大公约数的暴力法和辗转相除法，代码已给出清晰的实现。更相减损法的代码实现需要注意处理偶数和奇数的情况，以及在过程中记录约掉的2的次数。 - 在实现最大公约数算法后，通过上述公式可以很容易地计算最小公倍数。 4. **效率比较**： - 暴力法效率最低，因为需要遍历所有可能的公约数。 - 辗转相除法（欧几里得法）和更相减损法效率较高，尤其是欧几里得法，其时间复杂度为O(log min(a, b))，在大多数情况下是首选方法。 理解并掌握这些方法对于编写C语言程序解决整数的约分问题至关重要。在实际编程中，应根据具体需求和性能要求选择合适的算法。