首页
/ 正文

C 语言实例 – 求两数的最大公约数（千字长文）

更新时间: 2025-04-17 17:33:37

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

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

新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;

《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

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

在编程世界中，数学问题常常是算法学习的基石，而“求两数的最大公约数（GCD）”则是其中极具代表性的经典问题。无论是开发基础算法库，还是解决实际工程中的数值计算需求，掌握这一技能都能为开发者提供强大的工具支持。本文将以 C 语言实例 为切入点，通过循序渐进的方式，带领读者从基础概念到代码实现，逐步掌握求解两数最大公约数的核心方法。

一、最大公约数（GCD）的基本概念

1.1 定义与数学表达

最大公约数（Greatest Common Divisor，GCD）是指能够同时整除两个整数的最大正整数。例如，对于数字 12 和 18，它们的公约数包括 1、2、3、6，其中最大的 6 即为它们的最大公约数。数学上，GCD 可以用符号表示为：
[ \text{GCD}(a, b) = \text{最大的正整数 } d \text{，使得 } d \mid a \text{ 且 } d \mid b ]

1.2 形象化理解

想象你有两块不同长度的布料，一块长 12 米，另一块长 18 米。你需要用一把最小的尺子，恰好能完整测量这两块布的长度，且不留余量。这把尺子的长度就是两数的最大公约数（即 6 米）。通过这样的比喻，可以直观理解 GCD 的核心思想：寻找共同的“测量单位”。

二、传统方法：循环减法

2.1 原理与实现思路

最直观的求解方法是 循环减法：通过不断用较大数减去较小数，直到两数相等时的值即为 GCD。例如，对于 12 和 18：

18 - 12 = 6 → 新数对为 12 和 6
12 - 6 = 6 → 新数对为 6 和 6
两数相等，GCD 为 6

2.2 C 语言代码示例

#include <stdio.h>  

int gcd_subtraction(int a, int b) {  
    while (a != b) {  
        if (a > b)  
            a -= b;  
        else  
            b -= a;  
    }  
    return a;  
}  

int main() {  
    int num1 = 12, num2 = 18;  
    printf("GCD of %d and %d is %d\n", num1, num2, gcd_subtraction(num1, num2));  
    return 0;  
}

2.3 缺点分析

虽然循环减法简单易懂，但其时间复杂度为 O(min(a, b))，在数值较大时效率较低。例如，求 1000 和 1 的 GCD 需要循环 999 次，显然不够高效。

三、经典算法：欧几里得算法

3.1 算法原理

欧几里得算法（Euclidean Algorithm）通过 模运算 极大地优化了计算效率。其核心思想是：
[ \text{GCD}(a, b) = \text{GCD}(b, a % b)
]
直到 b = 0 时，此时 a 即为 GCD。例如，对于 12 和 18：

18 % 12 = 6 → 新数对为 12 和 6
12 % 6 = 0 → 新数对为 6 和 0 → GCD 为 6

3.2 迭代实现

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

3.3 递归实现

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

3.4 效率对比

欧几里得算法的时间复杂度为 O(log(min(a, b)))，比循环减法快数个数量级。例如，计算 1000 和 1 的 GCD 仅需 1 次模运算。

四、进阶方法：更相减损术

4.1 算法背景

更相减损术源自中国古代《九章算术》，其原理与循环减法类似，但通过 偶数预处理 优化计算：

若两数均为偶数，则 GCD 为 2 × GCD(a/2, b/2)
若一数为偶数，另一数为奇数，则 GCD 为 GCD(a/2, b)
若两数均为奇数，则按 a - b 继续计算

4.2 C 语言代码实现

int gcd_subtractive(int a, int b) {  
    while (a != b) {  
        if (a % 2 == 0 && b % 2 == 0) {  
            a /= 2;  
            b /= 2;  
        } else if (a % 2 == 0) {  
            a /= 2;  
        } else if (b % 2 == 0) {  
            b /= 2;  
        } else {  
            if (a > b)  
                a = a - b;  
            else  
                b = b - a;  
        }  
    }  
    return a;  
}

4.3 适用场景

更相减损术在处理 大偶数 时效率较高，但其复杂度仍高于欧几里得算法，因此后者仍是更优选择。

五、扩展应用：扩展欧几里得算法

5.1 算法扩展

扩展欧几里得算法（Extended Euclidean Algorithm）不仅能求 GCD，还能找到满足 ax + by = GCD(a, b) 的整数 x 和 y（贝祖系数）。这对解决线性同余方程、RSA 密码学等领域至关重要。

5.2 C 语言实现

void extended_gcd(int a, int b, int *x, int *y) {  
    if (b == 0) {  
        *x = 1;  
        *y = 0;  
        return;  
    }  
    extended_gcd(b, a % b, x, y);  
    int temp = *x;  
    *x = *y;  
    *y = temp - (a / b) * (*y);  
}  

int main() {  
    int a = 35, b = 15;  
    int x, y;  
    extended_gcd(a, b, &x, &y);  
    printf("GCD: %d, x = %d, y = %d\n", a*x + b*y, x, y);  
    return 0;  
}

5.3 实际意义

通过贝祖系数，可解方程 35x + 15y = 5，例如 x = 1, y = -2 是一组解，这为后续算法提供了数学基础。

六、代码优化与边界条件处理

6.1 处理负数与零

在实际编程中，需考虑输入为负数或零的情况。例如，GCD 的定义要求输入为正整数，因此可添加绝对值处理：

int gcd(int a, int b) {  
    a = abs(a);  
    b = abs(b);  
    // 继续执行欧几里得算法  
}

6.2 性能优化技巧

提前返回零值：若输入为零，直接返回非零数的绝对值。
预处理偶数：在欧几里得算法中，若两数均为偶数，可提前除以 2 并记录因子。

七、总结与实践建议

通过本文的讲解，读者已掌握了从基础到进阶的多种 C 语言实例 求解最大公约数的方法。关键知识点包括：

GCD 的数学定义与应用场景
循环减法、欧几里得算法及更相减损术的实现差异
扩展欧几里得算法的扩展功能

实践建议：

尝试用不同算法对比执行时间，理解效率差异。
将 GCD 函数封装为库函数，供后续项目复用。
探索 GCD 在分数约分、RSA 密钥生成等领域的实际应用。

掌握这一技能不仅能提升编程能力，更能为后续学习更复杂的算法（如 RSA 加密、中国剩余定理）奠定坚实基础。希望本文能成为你算法学习旅程中的一个清晰起点！