c语言求两个数的最大公约数

在C语言中，求两个数的最大公约数（GCD）可以使用辗转相除法（欧几里得算法），这是最常用且高效的方法,以下是几种实现方式：

方法1：辗转相除法（递归实现）

#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);
    // 确保输入为正数
    num1 = (num1 > 0) ? num1 : -num1;
    num2 = (num2 > 0) ? num2 : -num2;
    int result = gcd(num1, num2);
    printf("最大公约数是: %d\n", result);
    return 0;
}

说明：

1. 递归终止条件：当 b 为 0 时，a 即为最大公约数。
2. 递归过程：用 a % b 替换 a，b 替换 b，继续递归直到 b=0。

方法2：迭代实现（非递归）

#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);
    num1 = (num1 > 0) ? num1 : -num1;
    num2 = (num2 > 0) ? num2 : -num2;
    int result = gcd(num1, num2);
    printf("最大公约数是: %d\n", result);
    return 0;
}

说明：

• 通过循环不断更新 a 和 b 的值，直到 b 为 0，a 即为结果。

方法3：更高效的算法（二进制GCD）

对于大数，可以使用二进制GCD算法（Stein算法），它避免了取模运算,效率更高：

#include <stdio.h>
// 二进制GCD算法
int gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    // 找到公因子2的幂
    int shift;
    for (shift = 0; ((a | b) & 1) == 0; ++shift) {
        a >>= 1;
        b >>= 1;
    }
    // 确保 a 是奇数
    while ((a & 1) == 0) {
        a >>= 1;
    }
    do {
        // 确保 b 是奇数
        while ((b & 1) == 0) {
            b >>= 1;
        }
        // 比较并更新 a 和 b
        if (a > b) {
            int temp = b;
            b = a;
            a = temp;
        }
        b = b - a;
    } while (b != 0);
    return a << shift;
}
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    num1 = (num1 > 0) ? num1 : -num1;
    num2 = (num2 > 0) ? num2 : -num2;
    int result = gcd(num1, num2);
    printf("最大公约数是: %d\n", result);
    return 0;
}

说明：

• 通过位运算（>> 和 &）代替取模,适合处理大数。

注意事项：

1. 输入处理：确保输入为正数（或取绝对值）。
2. 边界情况：如果其中一个数为 0,另一个数的绝对值即为GCD。
3. 性能：辗转相除法是最通用的方法,二进制GCD在大数时更优。

选择适合场景的方法即可，通常递归或迭代的辗转相除法已足够高效。