用C语言实现，编写函数得到最大公约数，至少用三种方法

除了刚才提到的辗转相除法和辗转相减法，下面介绍另外一种求最大公约数的方法：

方法三：质因数分解法

将两个数分别进行质因数分解，然后找到它们公共的质因数，最后将这些质因数的乘积即为它们的最大公约数。

C语言实现代码如下：

int gcd(int a, int b) {
    int max = a > b ? a : b;
    int min = a < b ? a : b;
    int prime[max + 1];
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= max; i++) {
        if (!prime[i]) {
            for (int j = i * 2; j <= max; j += i) {
                prime[j] = 1;
            }
        }
    }
    int factors[max + 1];
    memset(factors, 0, sizeof(factors));
    for (int i = 2; i <= max; i++) {
        if (!prime[i]) {
            int count1 = 0, count2 = 0;
            int temp = max;
            while (temp % i == 0) {
                count1++;
                temp /= i;
            }
            temp = min;
            while (temp % i == 0) {
                count2++;
                temp /= i;
            }
            if (count1 > 0 && count2 > 0) {
                factors[i] = 1;
            }
        }
    }
    int result = 1;
    for (int i = 2; i <= max; i++) {
        if (factors[i]) {
            result *= i;
        }
    }
    return result;
}

以上三种方法都是比较常用的求最大公约数的方法，它们的时间复杂度不同，但都不会超过O(n^2)，其中n是a和b的较大值。