C语言求最大公约数的几种写法与代码示例

最大公约数（Greatest Common Divisor，简称 GCD）是能同时整除两个整数的最大正整数。例如，12 和 18 的最大公约数是 6。求最大公约数常用于分数约分、比例化简、周期问题，以及最小公倍数计算。

在 C 语言中，实现最大公约数并不难，难点主要在边界：输入为零或负数时怎么办？两个输入都是零时如何约定？取负数的绝对值会不会溢出？下面从常用算法开始，逐步讨论这些问题，并给出可以直接编译运行的完整代码。

一、先明确输入范围与结果约定

通常把最大公约数定义为非负数。对于两个不同时为零的整数，最大公约数是正整数；工程代码还常约定 gcd(0, 0) = 0，这样接口能覆盖所有输入，也符合欧几里得算法的自然终止结果。需要注意，数学上也有资料将零和零的最大公约数视为未定义，或者不作定义。因此，如果接口面向明确的数学规格，应采用规格规定的约定；如果规格没有说明，最好在函数注释和测试中明确选用哪一种。

常见的入门实现只接受非负整数，例如 unsigned int。这样做能避免负数取绝对值的问题，适合输入范围本来就限定为非负数的场景。若函数需要接受有符号整数，则必须谨慎处理最小负数。例如，在常见的二进制补码平台上，INT_MIN 的绝对值无法由 int 表示；直接写 -x 或调用 abs(x)，可能产生未定义行为。

下面先用 unsigned int 展示基础算法，再给出能安全接收 intmax_t 负数的版本。两种接口解决的问题不同，不要把基础版未经检查地用于任意有符号输入。

二、欧几里得算法：最常用的写法

欧几里得算法也叫辗转相除法。它利用下面的关系：

gcd(a, b) = gcd(b, a % b)，其中 b != 0。

不断用较小的数去除较大的数，并把“除数、余数”作为下一轮参数。余数会逐轮减小，最终变成零；此时另一个数就是最大公约数。例如，计算 gcd(48, 18)：

• 48 % 18 = 12，问题变成 gcd(18, 12)。
• 18 % 12 = 6，问题变成 gcd(12, 6)。
• 12 % 6 = 0，结果为 6。

使用无符号整数时，可以这样实现：

#include <stdio.h>

unsigned int gcd(unsigned int a, unsigned int b)
{
    while (b != 0) {
        unsigned int remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int main(void)
{
    unsigned int a = 48;
    unsigned int b = 18;

    printf("gcd(%u, %u) = %u\n", a, b, gcd(a, b));
    printf("gcd(0, 18) = %u\n", gcd(0, 18));
    printf("gcd(0, 0) = %u\n", gcd(0, 0));

    return 0;
}

把代码保存为 gcd.c，可使用 cc -std=c11 -Wall -Wextra -O2 gcd.c -o gcd 编译。程序采用 gcd(0, 0) = 0 的约定：当 b 为零时，循环立即结束并返回 a。

循环开始时不要求 a >= b。如果 a < b，第一次取模的余数就是 a，接下来两个数会自然交换。因此，通常无需先比较大小或交换变量。

复杂度与适用场景

欧几里得算法是一般整数求 GCD 的首选。它的循环次数是对数级的；更严格地说，连续的斐波那契数会导致较多迭代，迭代次数仍与较小输入的位数呈线性关系。对普通整数和大多数实际任务而言，效率足够高，代码也容易审查。

它的关键限制是不能对零取模，所以循环条件必须保证 b != 0 后才计算 a % b。上述实现满足这个条件。不要将余数计算写在检查 b 的代码之前。

三、递归版欧几里得算法

同一个关系也可以直接写成递归。递归版更贴近数学定义，适合讲解算法或代码层级较浅的场合：

#include <stdio.h>

unsigned int gcd_recursive(unsigned int a, unsigned int b)
{
    if (b == 0) {
        return a;
    }

    return gcd_recursive(b, a % b);
}

int main(void)
{
    printf("gcd(1071, 462) = %u\n", gcd_recursive(1071, 462));
    return 0;
}

终止条件是 b == 0。若漏掉这个条件，函数会持续调用，最终导致栈耗尽。递归深度对普通整数通常不大，但它没有带来比循环版更好的渐近性能，也会使用调用栈；在强调可预测资源占用的嵌入式代码或严格限制栈空间的环境中，迭代版通常更合适。

递归参数同样是无符号整数，所以此代码并不直接接收负数。递归与循环只是表达形式不同，输入边界和零值约定并不会因此改变。

四、减法版：适合讲原理，不适合直接用于大数

如果 a 和 b 都是正整数，从较大的数中反复减去较小的数，最大公约数不变：

gcd(a, b) = gcd(a - b, b)（当 a > b > 0 时）。

据此可以写出下面的版本：

#include <stdio.h>

unsigned int gcd_by_subtraction(unsigned int a, unsigned int b)
{
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }

    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }

    return a;
}

int main(void)
{
    printf("gcd(48, 18) = %u\n", gcd_by_subtraction(48, 18));
    printf("gcd(0, 18) = %u\n", gcd_by_subtraction(0, 18));
    printf("gcd(0, 0) = %u\n", gcd_by_subtraction(0, 0));
    return 0;
}

这里必须先处理零。若其中一个数为零，进入 a != b 的循环后，非零数会不断减去零，程序无法推进。也要确保两个数都为正时才依靠相等条件结束。

减法版虽然直观，但可能需要很多轮。例如，一个数很大、另一个数为 1 时，需要执行大量减法。相比之下，取模版一次就能把大数缩减为余数。因此减法版主要用于解释不变量或处理非常小的输入，不应因为代码看起来简单就默认它更快。

五、二进制 GCD：避免取模的替代方案

二进制 GCD，也称 Stein 算法，利用整数的二进制性质，主要使用移位、比较和减法，不需要取模。它依据的规则包括：

• 两个数都为偶数时，gcd(a, b) = 2 * gcd(a / 2, b / 2)。
• 一个数为偶数、另一个为奇数时，去掉偶数的因子 2 不改变 GCD。
• 两个正奇数相减后得到偶数，可以继续利用前两条规则。

下面的实现限定使用 unsigned int，并单独处理零值：

#include <stdio.h>

unsigned int gcd_binary(unsigned int a, unsigned int b)
{
    unsigned int common_shift = 0;

    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }

    while (((a | b) & 1u) == 0u) {
        a >>= 1;
        b >>= 1;
        ++common_shift;
    }

    while ((a & 1u) == 0u) {
        a >>= 1;
    }

    do {
        while ((b & 1u) == 0u) {
            b >>= 1;
        }

        if (a > b) {
            unsigned int temporary = a;
            a = b;
            b = temporary;
        }

        b -= a;
    } while (b != 0);

    return a << common_shift;
}

int main(void)
{
    printf("gcd(48, 18) = %u\n", gcd_binary(48, 18));
    printf("gcd(0, 18) = %u\n", gcd_binary(0, 18));
    return 0;
}

零值检查不可省略，否则“同时为偶数”的循环可能在零输入下持续进行。此函数的参数和返回值仍然是无符号整数；它只适用于相应的非负整数范围。二进制 GCD 在某些硬件或特定工作负载下可能有优势，但现代处理器上的性能还取决于编译器、指令集和数据分布。除非测量或平台要求支持这一选择，否则欧几里得算法通常更简单。

六、接收负数：避免对最小负数直接取绝对值

如果函数要接受有符号整数，常见思路是先取绝对值，再调用无符号 GCD。然而，直接写 -x 并不对所有 intmax_t 值都安全：intmax_t 的最小负值没有对应的正值可由同一有符号类型表示。abs、labs、llabs 也不能解决“结果无法由返回类型表示”的问题。

C 对有符号整数转换为无符号整数规定了模 UINTMAX_MAX + 1 的转换结果。利用无符号减法的模运算，可以在不对有符号最小值取负的情况下取得其数学上的绝对值。下面的代码使用 uintmax_t 保存绝对值，并让 GCD 的结果也以无符号类型返回：

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

static uintmax_t magnitude(intmax_t value)
{
    uintmax_t converted = (uintmax_t)value;

    if (value < 0) {
        return (uintmax_t)0 - converted;
    }

    return converted;
}

static uintmax_t gcd_unsigned(uintmax_t a, uintmax_t b)
{
    while (b != 0) {
        uintmax_t remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

static uintmax_t gcd_signed(intmax_t a, intmax_t b)
{
    return gcd_unsigned(magnitude(a), magnitude(b));
}

int main(void)
{
    intmax_t a = -48;
    intmax_t b = 18;
    uintmax_t result = gcd_signed(a, b);

    printf("gcd(%" PRIdMAX ", %" PRIdMAX ") = %" PRIuMAX "\n",
           a, b, result);

    printf("gcd(INTMAX_MIN, 0) = %" PRIuMAX "\n",
           gcd_signed(INTMAX_MIN, 0));

    return 0;
}

这个实现支持标准提供的 intmax_t 取值范围，包括 INTMAX_MIN，因为绝对值保存在对应的最大无符号整数类型 uintmax_t 中。它不承诺返回值能转换回 intmax_t：例如，最小有符号整数的数学绝对值可能大于 INTMAX_MAX。如果调用方需要有符号结果，必须限制输入，或改为接受无符号结果。

magnitude 中的转换和减法有明确的无符号语义，并非依赖某个平台的补码表示。这个写法适用于常见的 C 实现和标准整数类型。若项目使用自定义整数类型、编译器扩展或外部数值库，应按其类型规格单独确认。

七、用最大公约数计算最小公倍数

两个整数 a 和 b 的最小公倍数通常满足：

lcm(a, b) = |a / gcd(a, b) * b|。

先除以 GCD，再乘另一个数，可以降低中间乘积溢出的风险。不过，这并不保证乘法一定安全；如果结果超出目标类型范围，仍然会溢出。对于无符号整数，超出范围会按模运算回绕，得到的数通常不再是期望的最小公倍数；对于有符号整数，溢出属于未定义行为。

还要处理 lcm(0, x) = 0，并避免在两个数为零时直接做除法。下面的示例仅在运算结果可由 uintmax_t 表示时返回成功：

#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

static uintmax_t gcd_u(uintmax_t a, uintmax_t b)
{
    while (b != 0) {
        uintmax_t remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

static bool lcm_u(uintmax_t a, uintmax_t b, uintmax_t *result)
{
    uintmax_t divisor;

    if (result == NULL) {
        return false;
    }

    if (a == 0 || b == 0) {
        *result = 0;
        return true;
    }

    divisor = gcd_u(a, b);

    if (a / divisor > UINTMAX_MAX / b) {
        return false;
    }

    *result = (a / divisor) * b;
    return true;
}

int main(void)
{
    uintmax_t result;

    if (lcm_u(12, 18, &result)) {
        printf("lcm(12, 18) = %" PRIuMAX "\n", result);
    } else {
        printf("结果超出可表示范围\n");
    }

    return 0;
}

示例中先检查 a / divisor > UINTMAX_MAX / b，再执行乘法。对正的 b，这个条件用于判断乘积是否超出无符号类型上限。类似的溢出检查应在乘法发生之前进行，不能先计算乘积再判断，因为那时结果可能已经回绕或触发未定义行为。

八、输入校验：算法正确不代表输入解析安全

上面的完整示例使用常量作为输入，避免把文本解析问题和 GCD 算法混在一起。实际程序若从用户或文件读取数字，不能假设输入一定合法。至少需要考虑：

• 输入是否成功读取，字段数量是否符合预期。
• 文本是否包含多余字符、非法字符或空白格式问题。
• 数字是否超出目标整数类型的范围。
• 符号是否符合接口约定，例如无符号输入是否允许前导负号。
• 解析结果转换到更窄类型时是否超出该类型范围。

对于可能越界的文本，简单地把 scanf("%d", &value) 当作完整的范围校验并不稳妥。数值转换无法由目标对象表示时，标准库输入转换存在不适合依赖的边界行为。更严谨的做法是读取字符串，再使用 strtoimax、strtoumax 等函数，并检查转换是否发生、errno 是否报告范围错误，以及结束指针是否指向合法的字符串末尾。若程序有固定输入协议，也应明确拒绝超长文本和尾随垃圾字符。

另外，strtoumax 对负号有其标准规定的转换行为，并不等于“自动拒绝负数”。若接口只允许非负输入，需要在解析层明确拒绝负号，或先采用有符号解析再检查符号。不要仅凭选择了无符号目标类型，就认为负数输入一定会报错。

九、常见错误汇总

1. 没有处理除数为零

在 C 中，整数除以零和取模的除数为零都没有定义。欧几里得算法应先判断 b != 0，再计算 a % b。对 gcd(0, 0) 的约定也应写进接口说明。

2. 对负数直接取绝对值

对有符号最小值取负数可能超出类型范围。基础实现应明确只接受非负数；若要接受负数，应安全转换到足够宽的无符号类型，并允许结果用无符号类型返回。

3. 使用递归却遗漏终止条件

递归版必须在 b == 0 时返回。否则参数不会正常收敛，最终可能导致栈耗尽。对资源敏感的代码，循环版更容易控制资源使用。

4. 误以为减法版总是等价于快速取模版

减法关系在相应正数条件下成立，但重复减法的次数可能很大。对于一般输入，欧几里得算法通常更实用。

5. 将结果强行放回有符号类型

有符号输入的最大公约数本身可能无法由原来的有符号类型表示。不要在没有范围检查的情况下把无符号绝对值或 GCD 转回 int、long 等类型。

6. 用乘法事后检查溢出

计算 a * b 后再判断结果是否异常，并不能可靠检测溢出。乘法前应通过除法边界判断，或使用平台提供且经过验证的溢出检测机制。

十、如何选择实现

如果没有特殊需求，推荐使用迭代欧几里得算法，并明确参数是非负数还是允许负数。基础函数可以采用无符号参数；需要处理有符号最小值时，则应使用安全转换，并以无符号类型表达可能超出有符号范围的结果。对于所有实现，都要写清 gcd(0, 0) 的约定，并对真实输入来源进行独立校验。

结语

C 语言求最大公约数，核心算法通常只需几行欧几里得循环；可靠性则取决于算法之外的细节：取模不能遇到零除数，负数的绝对值可能超出原类型，输入解析可能越界，后续计算也可能发生乘法溢出。先选好类型和接口约定，再选择迭代、递归或二进制写法，往往比追求代码最短更重要。