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

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

1、辗转相除法：

#include <stdio.h>

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 <stdio.h>

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 <stdio.h>

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 <stdio.h>

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