C 语言第24题：求两个正整数的最小公倍数

题目

求两个正整数的最小公倍数

思路

本题求两个正整数的最小公倍数 LCM。

先写求 GCD 的函数或代码段，再算 lcm = a / gcd * b（先除 GCD 再乘，比先乘 a*b 更不易溢出）；结果很大时用 long long。

解题分析

lcm(a,b)=a/gcd(a,b)*b，先写 gcd 再乘，顺序上先除 gcd 再乘 b 可减小中间值。两数很大时用 long long 存 lcm。

完整程序

#include <stdio.h>

static int gcd_int(int a, int b)
{
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }
    int g = gcd_int(a, b);
    long long lcm = (long long)a / g * b;
    printf("%lld\n", lcm);
    return 0;
}

运行示例

输入：

4 6

输出：

12

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

用定义枚举 lcm

从较大数开始每次加 max(a,b)，能同时整除即 lcm，仅适合小数据。

程序：

#include <stdio.h>

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }
    int m = a > b ? a : b;
    int step = m;
    while (m % a != 0 || m % b != 0) {
        m += step;
    }
    printf("%d\n", m);
    return 0;
}

运行示例

输入：

4 6

输出：

12