C语言实现求最大公约数的三种方法

C语言实现求最大公约数的三种方法

最大公约数是指两个或多个整数共有约数中的最大值。下面我们将介绍 C 语言实现求最大公约数的三种方法。

1.辗转相减法

辗转相减法的基本思想是用大数减去小数，然后再用得出的差值去减小的数，这样一直操作，直到所减两数相等。 代码如下：

int gcd(int x, int y) {
    while(x != y) {
        if(x > y) {
            x = x - y;
        } else {
            y = y - x;
        }
    }
    return x;
}

辗转相减法是一种很容易理解的方法，但是在 x 和 y 的数值非常大的时候，效率会比较低。

2. 乘除法

用较大数去除以较小数，再用除数去除余数，再用上一步的余数去除下一步的除数，如此反复直到余数为0为止，则最后的除数就是最大公约数。

代码如下：

int gcd(int x,int y) {
    int temp;
    while(x % y != 0) {
        temp = x % y;
        x = y;
        y = temp;
    }
    return y;
}

如果两个数中一个数很大，而另外一个数很小，那么这种方法比起上一种方法更加高效。

3. 更相减损术和移位相结合的方法

更相减损术和移位相结合的方法结合了辗转相减法和乘除法的优点。在每一轮循环中，我们需要将 x 和 y 分别进行移位操作，移位操作一共分为两种情况：

1. 当 x 和 y 均为偶数时，将 x 和 y 同时右移直到它们变成奇数时停止，此时，我们将 t 记为移动的次数。

2. 当 x 为奇数而 y 为偶数时，只对 y 进行右移操作，直到 y 为奇数时停止，此时我们重新回到第一种情况。

确定了移位次数 t 后，每次将 x 和 y 的绝对值进行减少，共减少 t 次。代码如下：

int gcd(int x,int y) {
    int factor = 1;
    while(x != 0 && y != 0) {
        if(x % 2 == 0 && y % 2 == 0) {
            x /= 2;
            y /= 2;
            factor *= 2;
        } else if(x % 2 == 0 && y % 2 == 1) {
            x /= 2;
        } else if(x % 2 == 1 && y % 2 == 0) {
            y /= 2;
        } else {
            if(x > y) {
                x -= y;
            } else {
                y -= x;
            }
        }
    }
    return x * factor;
}

这种方法可以在 x 和 y 均为大整数时，还能够得到较好的效果。我们来看个示例：

例如，对于 $x = 24$ 和 $y = 18$，我们来看一下三种方法的结果。

• 用辗转相减法求得最大公约数为6
• 用乘除法求得最大公约数为6
• 用更相减损术和移位相结合的方法求得最大公约数为6

因此，这三种方法都可以有效地求出两个数的最大公约数。