C语言和C++中求两个数的最大公约数的多种实现方式

C语言和C++中求两个数的最大公约数有多种实现方式，比如辗转相除法、穷举法、更相减损术、质因数分解法等。

辗转相除法

辗转相除法是一种比较常用的求两个数的最大公约数的算法，它的基本思想是：用较大的数除以较小的数，再用除数除以出现的余数，如此重复，直到余数是0为止，此时被除数即为两数的最大公约数。

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

穷举法

穷举法是一种比较简单的求两个数的最大公约数的算法，它的基本思想是：从两个数中较小的那个数开始，一直递减到1，每次减1，判断这两个数是否都能被这个数整除，如果都能被整除，则该数就是两数的最大公约数。

int gcd(int a, int b)
{
    int c;
    c = (a < b) ? a : b;
    while (c > 0)
    {
        if (a % c == 0 && b % c == 0)
            break;
        c--;
    }
    return c;
}

更相减损术

更相减损术也是一种比较常用的求两个数的最大公约数的算法，它的基本思想是：用较大的数减去较小的数，把差代替较大的数，继续用较小的数减去差，如此重复，直到差为0为止，此时较小的数即为两数的最大公约数。

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a - b;
        a = (c > b) ? c : b;
        b = (c > b) ? b : c;
    }
    return a;
}

质因数分解法

质因数分解法是一种比较简单的求两个数的最大公约数的算法，它的基本思想是：将两个数都分解为质因数的乘积，求出两个数中公有的质因数，将这些公有的质因数相乘，即可得到两个数的最大公约数。

int gcd(int a, int b)
{
    int c;
    c = a;
    while (c > 1)
    {
        if (a % c == 0 && b % c == 0)
            break;
        c--;
    }
    return c;
}