C语言实现最大公约数与最小公倍数

C语言实现最大公约数与最小公倍数

引用

CSDN

1.

https://blog.csdn.net/weixin_63356609/article/details/140782311

本文将介绍如何使用C语言求解两个整数的最大公约数（Greatest Common Divisor，GCD）和最小公倍数（Least Common Multiple，LCM）。我们将使用辗转相除法来计算最大公约数，并基于最大公约数来计算最小公倍数。

求最大公约数

辗转相除法（首选，因为简单快捷）

思路：

1. 将两整数求余 a % b = c
2. 如果 c = 0，则 b 为最大公约数
3. 如果 c != 0，则 a = b；b = c；继续从1开始执行
4. 也就是说该循环的是否继续的判断条件就是 c 是否为0

举例说明：

假设 a = 21，b = 28

1. c = a % b = 21 % 28 = 21，此时 c = 21 不为0
2. 执行 a = b，b = c，即 a = 28，b = 21
3. c = a % b = 28 % 21 = 7，此时 c = 7 不为0
4. 执行 a = b，b = c，即 a = 21，b = 7
5. c = a % b = 21 % 7 = 0，此时 c = 0 循环结束

求最小公倍数

最小公倍数计算公式： 最小公倍数 = 两个数之间的乘积 / 两个数之间的最大公因数

下面是完整的C语言程序实现：

#include <stdio.h>

int HCF(int, int); // 最大公约数函数声明
int LCD(int, int, int); // 最小公倍数函数声明

int main() {
    int a, b, h, l;
    printf("请输入两个数：");
    scanf("%d%d", &a, &b);
    h = HCF(a, b);
    l = LCD(a, b, h);
    printf("最大公约数是：%d\n最小公倍数是:%d", h, l);
    return 0;
}

// 最大公约数函数实现
int HCF(int a, int b) {
    int t, r;
    if (b > a) {
        t = b;
        b = a;
        a = t;
    }
    while ((r = a % b) != 0) {
        a = b;
        b = r;
    }
    return b;
}

// 最小公倍数函数实现
int LCD(int a, int b, int h) {
    return (a * b / h);
}

运行结果：