企源知识库

在C语言中，求两个整数的最大公约数(GCD)可以通过多种算法实现，以下是几种常见的方法：

1. 辗转相除法

int gcd(int a, int b) {
    if (b == 0) {
        return a；
    }
    return gcd(b, a % b)；
}

2. 更相减损法

int gcd(int a, int b) {
    if (a == b) {
        return a；
    }
    if (a > b) {
        return gcd(a - b, b)；
    }
    return gcd(a, b - a)；
}

3. 移位法

int gcd(int a, int b) {
    if (a == 0) {
        return b；
    }
    if (b == 0) {
        return a；
    }
    if ((a & 1) == 0 && (b & 1) == 0) {
        return 2 * gcd(a >> 1, b >> 1)；
    }
    if ((a & 1) == 0) {
        return gcd(a >> 1, b)；
    }
    if ((b & 1) == 0) {
        return gcd(a, b >> 1)；
    }
}

4. 穷举法

int gcd(int a, int b) {
    for (int i = min(a, b)； i > 0； i--) {
        if (a % i == 0 && b % i == 0) {
            return i；
        }
    }
    return 1；
}

5. 输入输出示例

#include <stdio.h>
int main() {
    int a, b；
    printf("请输入两个整数：")；
    scanf("%d%d", &a, &b)；
    printf("最大公约数是：%d\n", gcd(a, b))；
    return 0；
}

以上代码展示了如何使用C语言实现求最大公约数的几种方法。你可以选择其中任意一种方法，根据你的需要进行调整和使用。