在 C 语言中，求最大公约数（GCD，Greatest Common Divisor）的常见的四种方法（附带源代码）

在 C 语言中，求最大公约数（GCD，Greatest Common Divisor）的常见方法有三种：辗转相除法、更相减损法和辗转相减法。以下是这四种方法的简单实现：

1、辗转相除法：

#include int gcd(int a, int b) {    while (b != 0) {        int temp = b;        b = a % b;        a = temp;    }    return a;}int main() {    int num1 = 24;    int num2 = 36;    int result = gcd(num1, num2);    printf("GCD of %d and %d is %d\n", num1, num2, result);    return 0;}

2、更相减损法：

#include int gcd(int a, int b) {    while (a != b) {        if (a > b) {            a -= b;        } else {            b -= a;        }    }    return a;}int main() {    int num1 = 24;    int num2 = 36;    int result = gcd(num1, num2);    printf("GCD of %d and %d is %d\n", num1, num2, result);    return 0;}

3、辗转相减法：

#include int gcd(int a, int b) {    while (a != b) {        if (a > b) {            a -= b;        } else {            b -= a;        }    }    return a;}int main() {    int num1 = 24;    int num2 = 36;    int result = gcd(num1, num2);    printf("GCD of %d and %d is %d\n", num1, num2, result);    return 0;}

除了上述提到的三种常见的最大公约数求解方法（辗转相除法、更相减损法、辗转相减法），还有一些其他的方法，其中一种较为高效的方法是使用欧几里德算法，也即辗转相除法的递归版本。以下是使用欧几里德算法的实现：

#include int gcd(int a, int b) {    if (b == 0) {        return a;    } else {        return gcd(b, a % b);    }}int main() {    int num1 = 24;    int num2 = 36;    int result = gcd(num1, num2);    printf("GCD of %d and %d is %d\n", num1, num2, result);    return 0;}

这些方法都可以求得两个整数的最大公约数。选择哪种方法取决于具体的情况和性能要求。通常情况下，辗转相除法是最常用的方法，因为它在性能上相对较好。

希望你也学会了，更多编程请来二当家的素材网：https://www.erdangjiade.com