C 语言第23题：求两个正整数的最大公约数（欧几里得算法）

题目

从标准输入读入两个正整数 a 和 b，使用欧几里得算法（辗转相除法）计算并输出它们的最大公约数（GCD）。

输入格式：一行输入两个正整数 a 和 b，以空格分隔。

输出格式：输出一个整数，表示 a 和 b 的最大公约数，末尾换行。

数据范围与约定：1 ≤ a, b ≤ 10⁹。

思路与算法

1. 欧几里得辗转相除原理
数学原理：两数最大公约数等于较小数与两数相除余数的最大公约数，即 gcd(a, b) = gcd(b, a % b)。

2. 循环终止条件
循环执行 t = a % b; a = b; b = t;，直到余数 b == 0 时终止，此时的 a 即为最大公约数。算法时间复杂度为对数级 O(log(min(a, b)))。

完整程序

#include <stdio.h>

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }

    int x = a, y = b;
    // 欧几里得辗转相除法：gcd(x, y) = gcd(y, x % y)，直到余数为 0
    while (y) {
        int t = x % y;
        x = y;
        y = t;
    }

    // 循环退出时 y 为 0，上一轮的除数 x 即为最大公约数
    printf("%d\n", x);
    return 0;
}

运行示例

输入：

48 18

输出：

6

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

递归 gcd

程序：

#include <stdio.h>

static int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }
    printf("%d\n", gcd(a, b));
    return 0;
}

输入：

48 18

输出：

6