轻松掌握C语言最小公倍数算法（从零开始学会求最小公倍数）

如何用C语言计算最小公倍数？

计算最小公倍数最常用的方法是利用最大公约数（GCD）。数学上有这样一个公式：

LCM(a, b) = (a × b) / GCD(a, b)

因此，我们只需先写出求最大公约数的函数，再用上述公式即可求出最小公倍数。

步骤一：编写求最大公约数（GCD）的函数

我们可以使用欧几里得算法（辗转相除法）高效地求出 GCD：

int gcd(int a, int b) {    while (b != 0) {        int temp = b;        b = a % b;        a = temp;    }    return a;}

步骤二：利用 GCD 计算 LCM

有了 GCD 函数后，LCM 就很容易实现了：

int lcm(int a, int b) {    return (a * b) / gcd(a, b);}

完整示例程序

下面是一个完整的 C 语言程序，演示如何输入两个整数并输出它们的最小公倍数：

#include <stdio.h>// 求最大公约数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) {    return (a * b) / gcd(a, b);}int main() {    int num1, num2;    printf("请输入两个正整数: ");    scanf("%d %d", &num1, &num2);    // 确保输入为正数    if (num1 <= 0 || num2 <= 0) {        printf("请输入正整数！\n");        return 1;    }    int result = lcm(num1, num2);    printf("%d 和 %d 的最小公倍数是: %d\n", num1, num2, result);    return 0;}

为什么这个方法有效？

因为任意两个正整数 a 和 b 都满足：a × b = GCD(a, b) × LCM(a, b)。这是数论中的一个基本定理。因此，只要我们能高效地求出 GCD，就能快速得到 LCM。

小贴士：避免整数溢出

在实际编程中，如果 a 和 b 很大，a * b 可能会超出 int 类型的范围。更安全的写法是：

int lcm(int a, int b) {    return a / gcd(a, b) * b;  // 先除后乘，减少溢出风险}

总结

通过本教程，你已经学会了如何用C语言编程教程中最基础的方法实现LCM算法实现。记住关键点：先求 GCD，再用公式求 LCM。多练习几次，你就能熟练掌握这一经典算法！

希望这篇关于 C语言最小公倍数算法 的教程对你有帮助！动手试试吧～