c语言求两个整数的最大公约数和最小公倍数

C语言求两个整数的最大公约数和最小公倍数

以下是使用C语言计算两个整数的最大公约数(GCD)和最小公倍数(LCM)的完整代码：

#include <stdio.h>
// 函数声明
int gcd(int a, int b);
int lcm(int a, int b);
int main() {
    int num1, num2;
    // 输入两个整数
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    // 验证输入是否为正整数
    if (num1 <= 0 || num2 <= 0) {
        printf("请输入正整数！\n");
        return 1;
    }
    // 计算并输出结果
    printf("最大公约数(GCD)为: %d\n", gcd(num1, num2));
    printf("最小公倍数(LCM)为: %d\n", lcm(num1, num2));
    return 0;
}
// 使用欧几里得算法计算最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
// 计算最小公倍数
int lcm(int a, int b) {
    // 使用公式 LCM(a,b) = (a*b)/GCD(a,b)
    return (a * b) / gcd(a, b);
}

代码说明

1. 最大公约数(GCD)计算：

   

   • 使用欧几里得算法（辗转相除法）
   • 算法原理：gcd(a,b) = gcd(b, a mod b)，直到b为0时，a即为最大公约数

2. 最小公倍数(LCM)计算：

   

   • 使用公式：LCM(a,b) = (a × b) / GCD(a,b)
   • 这个公式基于最大公约数和最小公倍数的关系

3. 输入验证：

   确保输入的是正整数，因为GCD和LCCM通常针对正整数定义

示例运行

请输入两个正整数: 12 18
最大公约数(GCD)为: 6
最小公倍数(LCM)为: 36

其他实现方法

除了欧几里得算法,还可以使用以下方法计算GCD：

更相减损法

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

递归实现欧几里得算法

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

代码提供了多种实现方式,可以根据需要选择最适合的方法。