c语言实现最大公约数

要在C语言中实现最大公约数，可以使用辗转相除法或更相减损术两种方法。

辗转相除法的实现代码如下所示：

#include <stdio.h>

int gcd1(int x, int y) {
    int z = x % y;
    while (z) {
        x = y;
        y = z;
        z = x % y;
    }
    return y;
}

int main() {
    int a = 98;
    int b = 63;
    int max1 = gcd1(a, b);
    printf("%d和%d的最大公约数为%d\n", a, b, max1);
    return 0;
}

更相减损术的实现代码如下所示：

#include <stdio.h>

int gcd2(int x, int y) {
    int sum1 = 1;
    while ((x % 2 == 0) && (y % 2 == 0)) {
        sum1 *= 2;
        x = x / 2;
        y = y / 2;
    }
    while (1) {
        if (x < y) {
            int temp = x;
            x = y;
            y = temp;
        }
        int s = x - y;
        if (y == s)
            break;
        else {
            x = y;
            y = s;
        }
    }
    return y * sum1;
}

int main() {
    int a = 98;
    int b = 63;
    int max2 = gcd2(a, b);
    printf("%d和%d的最大公约数为%d\n", a, b, max2);
    return 0;
}

辗转相除法的实现过程是通过除数和余数的反复做除法运算，直到余数为0时取当前算式的除数为最大公约数。而更相减损术是首先判断两个数的奇偶性，然后通过不断减去两个数中较小的数，直到两个数相等为止，最后再将得到的结果与约掉的若干个2的积相乘，得到最大公约数。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>