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

方法一：辗转相除法

辗转相除法，又称欧几里得算法，是求最大公约数的一种常用方法。

C语言实现代码如下：

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

方法二：辗转相减法

辗转相减法是另一种求最大公约数的常用方法。

C语言实现代码如下：

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

以上两种方法都是比较常用的求最大公约数的方法，它们的时间复杂度都是O(logn)，其中n是a和b的较大值。

相关问题

用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的较大值。

用C语言实现，编写函数得到最小公倍数，至少用两种方法

除了上面提到的利用最大公约数求最小公倍数的方法外，还可以使用以下两种方法来实现求最小公倍数的函数：

方法一：暴力枚举法

此方法的思路是从两个数的较大值开始，一直往上枚举，直到找到一个数，使得这两个数同时能被它整除。具体实现代码如下：

int lcm(int a, int b) {
    int max = (a > b) ? a : b;
    while (1) {
        if (max % a == 0 && max % b == 0) {
            return max;
        }
        max++;
    }
}

方法二：倍增法

此方法的思路是将两个数进行分解质因数，然后把它们的公共因数取出来，最后再将这些公共因数乘起来。具体实现代码如下：

int lcm(int a, int b) {
    int max = (a > b) ? a : b;
    int min = (a < b) ? a : b;
    int lcm = max;
    while (lcm % min != 0) {
        lcm += max;
    }
    return lcm;
}

需要注意的是，以上两种方法都可以求得最小公倍数，但是它们的时间复杂度都比较高，不太适用于大数据的计算。因此，在实际的应用中，我们更多地会使用利用最大公约数来求最小公倍数的方法。