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

题目

求两个正整数的最大公约数（欧几里得算法）

思路

本题用欧几里得算法求两个正整数的最大公约数 GCD。

循环 while (b)：每次用余数更新 t=a%b; a=b; b=t，直到 b 为 0，此时 a 就是 GCD。题目保证正整数时可不必先交换大小。

解题分析

欧几里得算法反复用余数缩小问题：gcd(a,b)=gcd(b,a mod b)，直到余数为 0。辗转相除的 while 写法与手算一致；递归写法代码更短，层数在 log 量级内一般没问题。

完整程序

#include <stdio.h>

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }
    int x = a, y = b;
    while (y) {
        int t = x % y;
        x = y;
        y = t;
    }
    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