兩個或多個整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)，其中除0以外最小的一個公倍數(shù)就叫做這幾個整數(shù)的最小公倍數(shù)。整數(shù)a，b的最小公倍數(shù)記為[a，b]，同樣的，a，b，c的最小公倍數(shù)記為[a，b，c]，多個整數(shù)的最小公倍數(shù)也有同樣的記號。

.與最小公倍數(shù)相對應(yīng)的概念是最大公約數(shù)，a，b的最大公約數(shù)記為（a，b）。關(guān)于最小公倍數(shù)與最大公約數(shù)，我們有這樣的定理：(a,b)x[a,b]=ab(a,b均為整數(shù))。

——百度百科

我們可以通過兩個方法求最小公倍數(shù)。

第一種是窮舉法，列舉所以可能的數(shù)，直到找到最小的公倍數(shù)；第二種是使用最小公倍數(shù)與最大公約數(shù)的一個定理——兩個整數(shù)的最小公倍數(shù)等于兩數(shù)之積除以兩個數(shù)的最大公因數(shù)，即(a,b)x[a,b]=ab（(a,b)表示a和b的最大公約數(shù)，[a,b]表示a和b的最小公倍數(shù)，a，b均為整數(shù)）

方法一：窮舉法

假設(shè)有兩個整數(shù)num1和num2，這兩個整數(shù)的最小公倍數(shù)一定大于等于它們的最大值，同時小于等于它們的積。

按從小到大的順序遍歷整個范圍內(nèi)的所有整數(shù)，第一個公因數(shù)即為它們的最小公倍數(shù)。

【不考慮負(fù)數(shù)，求負(fù)數(shù)的最小公倍數(shù)本就是無意義的（相當(dāng)于求兩個正數(shù)的最大公倍數(shù)）】

#include <stdio.h>

/**
 * @brief 獲取最小公倍數(shù)（窮舉法）
 * @param num1 第一個正整數(shù)
 * @param num2 第一個正整數(shù)
 * @return 返回最小公倍數(shù)
 */
int Get_Min_Comm_Multiple(int num1, int num2)
{
    int i = 0, tmp = 0, mul = 0;
    tmp = num1 > num2 ? num1 : num2; //獲取最大值
    mul = num1 * num2;   //兩數(shù)之積
    for(i = tmp; i <= mul; i++)
    {
        //同時為num1和num2的倍數(shù)
        if(i % num1 == 0 && i % num2 == 0)
            break;
    }
    return i;
}

int main()
{
    int num1, num2;

    printf("請輸入兩個正整數(shù)\n");
    scanf("%d%d", &num1, &num2);
    printf("它們的最小公倍數(shù)為：%d\n",Get_Min_Comm_Multiple(num1, num2));
    return 0;
}

運(yùn)行結(jié)果

方法二：定理法

使用定理求最小公倍數(shù)（兩個整數(shù)的最小公倍數(shù)等于兩數(shù)之積除以兩個數(shù)的最大公因數(shù)），需要先求出兩個整數(shù)的最大公因數(shù)，最大公因數(shù)這里采用輾轉(zhuǎn)相除法。（最大公因數(shù)的求法可以參考我上一篇文章——第68天：求最大公約數(shù)（使用三種方法））

【不考慮負(fù)數(shù)，求負(fù)數(shù)的最小公倍數(shù)本就是無意義的（相當(dāng)于求兩個正數(shù)的最大公倍數(shù)）】

#include <stdio.h>

/**
 * @brief 獲取兩個正整數(shù)的最大公因數(shù)（輾轉(zhuǎn)相除法）
 * @param num1  第一個正整數(shù)
 * @param num2  第二個正整數(shù)
 * @return      最大公因數(shù)
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    int remainder = num1 % num2;  //余數(shù)

    while(remainder != 0)
    {
        num1 = num2;      //更新被除數(shù)
        num2 = remainder; //更新除數(shù)
        remainder = num1 % num2; //更新余數(shù)
    }
    return num2;  //最后的除數(shù)即為最大公因數(shù)
}

/**
 * @brief 獲取最小公倍數(shù)（定理法）
 * @param num1 第一個正整數(shù)
 * @param num2 第一個正整數(shù)
 * @return 返回最小公倍數(shù)
 */
int Get_Min_Comm_Multiple(int num1, int num2)
{
    /* 最小公倍數(shù) = 兩數(shù)相乘 / 最大公因數(shù) */
    return num1 * num2 / Get_Max_Comm_Divisor(num1, num2);
}

int main()
{
    int num1 = 0, num2 = 0;

    printf("請輸入兩個正整數(shù)\n");
    scanf("%d%d", &num1, &num2);
    printf("它們的最小公倍數(shù)為：%d\n", Get_Min_Comm_Multiple(num1, num2));
    return 0;
}

運(yùn)行結(jié)果