C语言如何求两个整数的最大公约数？

方法1：辗转相除法（欧几里得算法）

这是最常用且高效的方法，基于数学原理：gcd(a, b) = gcd(b, a % b),递归或迭代实现。

递归实现

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

迭代实现

#include <stdio.h>
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main() {
    int num1, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数是: %d\n", gcd(num1, num2));
    return 0;
}

方法2：更相减损术

基于数学原理：gcd(a, b) = gcd(a - b, b)（假设 a > b）,逐步减小数值直到相等。

#include <stdio.h>
int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}
int main() {
    int num1, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数是: %d\n", gcd(num1, num2));
    return 0;
}

方法3：暴力枚举法

从较小数开始向下枚举,直到找到能同时整除两个数的最大数。

#include <stdio.h>
int gcd(int a, int b) {
    int min = (a < b) ? a : b;
    for (int i = min; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1; // 理论上不会执行到这里
}
int main() {
    int num1, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数是: %d\n", gcd(num1, num2));
    return 0;
}

注意事项

1. 输入处理：确保输入的是非负整数（负数需取绝对值）。
2. 效率：辗转相除法（方法1）效率最高,尤其适合大数。
3. 边界情况：如果其中一个数为0,GCD是另一个数的绝对值。

扩展：处理负数

如果输入可能是负数,可以在计算前取绝对值：

#include <stdlib.h> // 用于 abs()
int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

• 推荐方法：辗转相除法（迭代或递归）,效率高且代码简洁。
• 其他方法：更相减损术（适合教学）、暴力枚举（简单但效率低）。

选择合适的方法即可满足需求！