C语言四种方法求最大公约数

在 C 语言中，有几种方法可以求最大公约数（GCD）：欧几里得算法、辗转相除法、更相减损法和穷举法。以下分别介绍这四种方法的实现示例：

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, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);

    printf("最大公约数为: %d\\n", result);

    return 0;
}

1. 更相减损法：

#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, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);

    printf("最大公约数为: %d\\n", result);

    return 0;
}

1. 辗转相除法（递归实现）：

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    int num1, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);

    printf("最大公约数为: %d\\n", result);

    return 0;
}

1. 穷举法（循环遍历求解）：

#include <stdio.h>

int gcd(int a, int b) {
    int min = (a < b) ? a : b;
    for (int i = min; i >= 1; --i) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;  // 如果没有找到公约数，默认返回1
}

int main() {
    int num1, num2;
    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);

    printf("最大公约数为: %d\\n", result);

    return 0;
}

这些示例程序分别演示了使用不同方法求解最大公约数的过程。可以根据需要选择适合的方法。