C语言编程题计算最大公约数

1、辗转相除法（欧几里德算法）

求两个数最大公约数最常用的方法之一，其原理是利用两个数的除法余数的递归来求解。

#include <stdio.h>

// 函数声明：计算最大公约数
int gcd(int a, int b);

int main() {
    int num1, num2;

    // 输入两个整数
    printf("请输入两个整数：\n");
    scanf("%d %d", &num1, &num2);

    // 调用函数计算最大公约数
    int result = gcd(num1, num2);

    // 输出最大公约数
    printf("最大公约数是：%d\n", result);

    return 0;
}

// 函数定义：计算最大公约数（辗转相除法）
int gcd(int a, int b) {
    int temp;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

2、递归实现辗转相除法

使用递归方式实现辗转相除法求最大公约数。

#include <stdio.h>

// 函数声明：计算最大公约数
int gcd(int a, int b);

int main() {
    int num1, num2;

    // 输入两个整数
    printf("请输入两个整数：\n");
    scanf("%d %d", &num1, &num2);

    // 调用函数计算最大公约数
    int result = gcd_recursive(num1, num2);

    // 输出最大公约数
    printf("最大公约数是：%d\n", result);

    return 0;
}

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

3、更相减损术

古老的方法，通过连续减小较大数和较小数的差来求最大公约数。

#include <stdio.h>

// 函数声明：计算最大公约数
int gcd(int a, int b);

int main() {
    int num1, num2;

    // 输入两个整数
    printf("请输入两个整数：\n");
    scanf("%d %d", &num1, &num2);

    // 调用函数计算最大公约数
    int result = gcd_subtraction(num1, num2);

    // 输出最大公约数
    printf("最大公约数是：%d\n", result);

    return 0;
}

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

4、穷举法

从较小的数开始递减，找到两个数都能整除的最大数。

#include <stdio.h>

// 函数声明：计算最大公约数
int gcd(int a, int b);

int main() {
    int num1, num2;

    // 输入两个整数
    printf("请输入两个整数：\n");
    scanf("%d %d", &num1, &num2);

    // 调用函数计算最大公约数
    int result = gcd_brute_force(num1, num2);

    // 输出最大公约数
    printf("最大公约数是：%d\n", result);

    return 0;
}

int gcd_brute_force(int a, int b) {
    int gcd = 1;
    for (int i = 1; i <= a && i <= b; ++i) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

5、位操作法

利用位运算的性质来求解，效率较高。

#include <stdio.h>

// 函数声明：计算最大公约数
int gcd(int a, int b);

int main() {
    int num1, num2;

    // 输入两个整数
    printf("请输入两个整数：\n");
    scanf("%d %d", &num1, &num2);

    // 调用函数计算最大公约数
    int result = gcd_bitwise(num1, num2);

    // 输出最大公约数
    printf("最大公约数是：%d\n", result);

    return 0;
}

int gcd_bitwise(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    int shift;
    for (shift = 0; ((a | b) & 1) == 0; ++shift) {
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0) a >>= 1;
    do {
        while ((b & 1) == 0) b >>= 1;
        if (a > b) {
            unsigned int t = b; b = a; a = t;
        }
        b = b - a;
    } while (b != 0);
    return a << shift;
}