异常教程

C 练习实例16 – 最大公约数和最小公倍数（手把手讲解）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

在编程学习的旅程中，数学问题始终是一个重要且有趣的领域。本文将围绕 “C 练习实例16 – 最大公约数和最小公倍数” 展开，通过深入浅出的讲解，帮助读者理解这两个基础概念，并掌握其实现方法。无论是编程初学者还是希望巩固算法基础的开发者，都能通过本文获得实用的技巧和启发。

一、数学基础：最大公约数（GCD）与最小公倍数（LCM）

1.1 最大公约数（GCD）的定义

最大公约数（Greatest Common Divisor，简称 GCD）是指两个或多个整数共有约数中最大的一个。例如，数字 8 和 12 的公约数包括 1、2、4，其中最大的是 4，因此它们的 GCD 是 4。
形象比喻：可以想象两个人分糖果，如果两人分到的糖果数量必须相等且没有剩余，那么最大公约数就是两人能分到的“最大相同数量”。

1.2 最小公倍数（LCM）的定义

最小公倍数（Least Common Multiple，简称 LCM）是指两个或多个整数公有的倍数中最小的一个。例如，数字 3 和 5 的公倍数有 15、30、45 等，其中最小的是 15，因此它们的 LCM 是 15。
形象比喻：假设两个人以不同步速走路，最小公倍数就是他们再次同时到达起点所需的最短时间。

1.3 数学关系：GCD 与 LCM 的联系

GCD 和 LCM 之间存在一个核心公式：
[ \text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)} ]
这个公式表明，只要求出 GCD，就能轻松计算 LCM。因此，实现 GCD 的算法是解决问题的关键。

二、算法实现：如何计算 GCD？

2.1 穷举法（Brute Force）

穷举法是最直观但效率最低的方法。其核心思想是遍历从 1 到较小数的所有整数，找到能同时整除两个数的最大值。

#include <stdio.h>  

int gcd_brute_force(int a, int b) {  
    int min = (a < b) ? a : b;  
    for (int i = min; i >= 1; i--) {  
        if (a % i == 0 && b % i == 0) {  
            return i;  
        }  
    }  
    return 1; // 最小公约数为 1  
}  

int main() {  
    int a = 8, b = 12;  
    printf("GCD of %d and %d is %d\n", a, b, gcd_brute_force(a, b));  
    return 0;  
}

优缺点分析：
| 特点 | 优点 | 缺点 |
|---------------------|-----------------------------|-----------------------------|
| 时间复杂度 | O(n)，n 为较小数的值 | 对大数效率极低 |
| 适用场景 | 小规模数据或教学演示 | 不适合实际开发或大规模计算 |

2.2 欧几里得算法（Euclidean Algorithm）

欧几里得算法是计算 GCD 的经典方法，其核心公式为：
[ \text{GCD}(a, b) = \text{GCD}(b, a % b) \quad \text{（当 } b \neq 0 \text{ 时）}
]
当 ( b = 0 ) 时，( a ) 即为 GCD。

2.2.1 迭代实现

int gcd_euclidean_iterative(int a, int b) {  
    while (b != 0) {  
        int temp = b;  
        b = a % b;  
        a = temp;  
    }  
    return a;  
}

2.2.2 递归实现

int gcd_euclidean_recursive(int a, int b) {  
    if (b == 0) {  
        return a;  
    }  
    return gcd_euclidean_recursive(b, a % b);  
}

效率对比：
欧几里得算法的时间复杂度为 O(log(min(a, b)))，远优于穷举法。例如，计算 ( \text{GCD}(1000000, 999999) ) 时，穷举法需要遍历 100 万次，而欧几里得算法仅需约 10 次迭代。

三、代码示例与完整实现

3.1 完整程序：C 练习实例16 的标准实现

#include <stdio.h>  

// 欧几里得算法（递归实现）  
int gcd(int a, int b) {  
    return b == 0 ? a : gcd(b, a % b);  
}  

// 计算 LCM 的函数  
int lcm(int a, int b) {  
    return (a * b) / gcd(a, b);  
}  

int main() {  
    int num1, num2;  
    printf("Enter two integers: ");  
    scanf("%d %d", &num1, &num2);  

    int result_gcd = gcd(num1, num2);  
    int result_lcm = lcm(num1, num2);  

    printf("GCD of %d and %d is: %d\n", num1, num2, result_gcd);  
    printf("LCM of %d and %d is: %d\n", num1, num2, result_lcm);  

    return 0;  
}

3.2 输入输出示例

Enter two integers: 24 36  
GCD of 24 and 36 is: 12  
LCM of 24 and 36 is: 72

四、进阶优化：Stein 算法（Binary GCD）

欧几里得算法虽然高效，但在某些场景下仍可优化。Stein 算法（也称二进制 GCD）通过二进制运算进一步提升效率，尤其适合处理大整数。

4.1 核心思想

  • 性质 1：若 ( a ) 和 ( b ) 均为偶数，则 ( \text{GCD}(a, b) = 2 \times \text{GCD}(a/2, b/2) )。
  • 性质 2：若 ( a ) 为偶数，( b ) 为奇数，则 ( \text{GCD}(a, b) = \text{GCD}(a/2, b) )。
  • 性质 3：若 ( a ) 和 ( b ) 均为奇数，则 ( \text{GCD}(a, b) = \text{GCD}(b, a - b) )。

4.2 代码实现

int gcd_stein(int a, int b) {  
    if (a == 0) return b;  
    if (b == 0) return a;  

    if (a % 2 == 0 && b % 2 == 0) {  
        return 2 * gcd_stein(a / 2, b / 2);  
    } else if (a % 2 == 0) {  
        return gcd_stein(a / 2, b);  
    } else if (b % 2 == 0) {  
        return gcd_stein(a, b / 2);  
    } else {  
        return gcd_stein(b, a < b ? b - a : a - b);  
    }  
}

效率对比：
对于二进制数，Stein 算法的效率比欧几里得算法更高，尤其是在硬件支持位运算的场景下（如嵌入式系统）。

五、实际案例与应用

5.1 简化分数

假设有一个分数 ( \frac{48}{60} )，通过计算 GCD（即 12），可将其简化为 ( \frac{4}{5} )。

5.2 时间同步问题

假设两个事件分别每 6 分钟和 9 分钟发生一次，它们的 LCM（即 18 分钟）就是两者同时发生的最短时间间隔。

六、常见问题与调试技巧

6.1 问题：负数输入如何处理？

  • 解决方案：将输入的负数转换为正数再计算，因为 GCD 和 LCM 均为正数。
int a = -24, b = -36;  
printf("GCD: %d", gcd(abs(a), abs(b)));

6.2 问题：当输入为 0 时如何处理？

  • 解决方案：若其中一个数为 0，则 GCD 为另一个数的绝对值。例如，( \text{GCD}(0, 5) = 5 )。

七、结论

通过本文的讲解，我们系统学习了 “C 练习实例16 – 最大公约数和最小公倍数” 的实现方法，包括算法原理、代码示例和优化技巧。无论是编程初学者通过穷举法理解基础概念，还是开发者通过欧几里得或 Stein 算法提升效率，都能在实际项目中灵活应用这些知识。
未来，当遇到需要处理整数关系的问题时（如分数运算、时间同步、密码学等场景），掌握 GCD 和 LCM 的计算方法将成为解决问题的有力工具。

希望本文能为你的编程学习之路提供一份清晰的指南！

最新发布

查看更多文章