最小公倍数

暴力法

找到a,b中的较大值，假设是最小公倍数，然后去整除，不能整除就++，直到找到最小公倍数为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int a = 12;
    int b = 16;
    if (a < b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    int i = 0;
    for (i = a;; i++)
    {
        if (i % a == 0 && i % b == 0)
        {
            break;
        }
    }
    printf("%d is lowest common multiple", i);

    return 0;
}

搭配辗转相除法求最小公倍数

最小公倍数 = 两数乘积 / 最大公因数

先使用辗转相除法求最大公约数，然后根据最大公约数和两数的乘积计算最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    int a = 12;
    int b = 16;
    int z = a * b;   // 两数乘积
    int c = 0;
    while (c = a % b)
    {
        a = b;
        b = c;
    }
    int lcm = z / b;
    printf("%d is lowest common multiple", lcm);
    return 0;
}