C语言计算最大公约数的四种方法与代码实现

1. 准备条件与标准函数框架

在所有算法实现中，首先需要明确输入为正整数的约束。若输入包含零或负数，通常视为无效输入。为了统一接口规范，以下所有算法均封装为名为 Gcd 的函数，并在输入非法时返回 -1。

2. 穷举法：基于定义的直观实现

穷举法遵循最大公约数的数学定义：寻找能同时整除两个数的最大整数。由于最大公约数不可能超过两个数中的较小者，因此算法从较小值开始向下遍历至1，第一个满足整除条件的数即为结果。

第1步：确定搜索范围

比较输入的两个整数 a 和 b，取较小值作为初始循环变量 t。

第2步：迭代验证

从 t 开始逐次递减，检查当前值是否同时整除 a 和 b。一旦找到满足 a % i == 0 && b % i == 0 的 i，立即返回该值。

// 穷举法实现
int Gcd(int a, int b)
{
    int i, t;
    // 输入验证：必须为正整数
    if (a <= 0 || b <= 0)
        return -1;
    
    // 取较小值作为起始点
    t = a < b ? a : b;
    
    // 从t向下尝试，找到第一个公约数即为最大公约数
    for (i=t; i>0; i--)
    {
        if (a%i==0 && b%i==0)
            return i;
    }
    return 1; // 理论上不会执行至此，因为1必为公约数
}

该方法逻辑简单，但时间复杂度较高，约为 O(min(a, b))。当两数较大且互质时，循环次数极大，效率较低，仅适用于小规模数据或教学演示。

3. 欧几里得算法（辗转相除法）

这是最常用的GCD算法，其核心原理基于数学定理：Gcd(a, b) = Gcd(b, a % b)。算法通过反复取余运算，直到余数为0，此时的除数即为最大公约数。

第1步：循环取余

计算 r = a % b。若 r != 0，则将 b 赋值给 a，将 r 赋值给 b，重复此过程。

第2步：终止判断

当余数 r 为0时，当前的 a（即上一轮的除数）即为最大公约数。

// 辗转相除法 - 迭代实现
int Gcd(int a, int b)
{
    int r;
    if (a <= 0 || b <= 0)
        return -1;
    do {
        r = a % b;
        a = b;
        b = r;
    } while (r != 0);
    return a;
}

第3步：递归优化（可选）

利用相同逻辑可改写为递归形式，代码更为简洁：

// 辗转相除法 - 递归实现
int Gcd(int a, int b)
{
    if (a <= 0 || b <= 0)
        return -1;
    if (a % b == 0)
        return b;
    else
        return Gcd(b, a % b);
}

辗转相除法的时间复杂度接近对数级别 O(log min(a, b))，在处理大整数时性能显著优于穷举法。

4. 更相减损法与递归应用

该方法源于《九章算术》，依据性质：若 a > b，则 Gcd(a, b) = Gcd(a-b, b)。通过反复减去较小数直至两数相等，得到的值即为GCD。

第1步：非递归减法实现

当 a != b 时，若 a > b 则 a = a - b，否则 b = b - a，直到 a == b。

// 更相减损法 - 迭代实现
int Gcd(int a, int b)
{
    if (a <= 0 || b <= 0)
        return -1;
    while (a != b)
    {
        if (a > b)
            a = a - b;
        else 
            b = b - a;
    }
    return a;
}

第2步：递归实现

将上述逻辑转化为递归调用：

// 更相减损法 - 递归实现
int Gcd(int a, int b)
{
    if (a <= 0 || b <= 0)
        return -1;
    if (a == b)
        return a;
    else if (a > b)
        return Gcd(a-b, b);
    else
        return Gcd(a, b-a);
}

虽然此法易于理解，但在两数差距较大时（如1和100），减法次数远多于取余次数，效率低于辗转相除法。

5. 主函数测试与调用示例

以下是整合输入验证与结果输出的标准主函数，可用于测试上述任意一种 Gcd 实现：

#include <stdio.h>

// 声明函数（此处替换为选用的Gcd实现）
int Gcd(int a, int b);

int main(void)
{
    int a, b, c;
    printf("Input a,b:");
    // 注意：scanf格式中的逗号需与用户输入的标点一致
    scanf("%d,%d", &a, &b); 
    
    c = Gcd(a, b);
    if (c != -1)
        printf("Greatest Common Divisor of %d and %d is %d\n", a, b, c);
    else
        printf("Input number should be positive!\n");
        
    return 0;
}

6. 独立测试脚本：更相减损法直出版

若无需模块化拆分，可直接在主函数中实现更相减损逻辑进行快速验证：

#include<stdio.h>

int main()
{
    int m, n;
    printf("请输入两个正整数:");
    scanf("%d %d", &m, &n);
    
    printf("%d和%d的最大公约数是", m, n);
    
    // 循环相减直到两数相等
    while(m != n)
    {
        if(m > n)
            m = m - n;
        else
            n = n - m;
    }
    
    printf("%d\n", n);
    return 0;
}

总结

计算最大公约数是编程入门的经典案例。穷举法适合理解基本概念，辗转相除法在性能和通用性上最优，更相减损法则展示了数学变换在算法中的应用。在实际开发中，建议优先使用辗转相除法（迭代或递归版本），并始终包含对非正整数的异常处理机制。 以上就是C语言求两个正整数最大公约数的详细内容，更多关于C语言最大公约数算法优化的资料请关注本站其它相关文章！