日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言實現求解最小公倍數的算法示例_C 語言

作者：小輝_Super ? 更新時間： 2022-03-13 編程語言

題目描述

求任意兩個正整數的最小公倍數

問題分析

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

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

——百度百科

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

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

方法一：窮舉法

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

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

【不考慮負數，求負數的最小公倍數本就是無意義的（相當于求兩個正數的最大公倍數）】

#include <stdio.h>

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

int main()
{
    int num1, num2;

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

運行結果

方法二：定理法

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

【不考慮負數，求負數的最小公倍數本就是無意義的（相當于求兩個正數的最大公倍數）】

#include <stdio.h>

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

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

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

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

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

運行結果

如果程序不作處理（不檢測輸入的數字是否為正數），此時輸入負數，也能返回一個公倍數，但不是“最小”公倍數，不過求負數的最小公倍數本就是無意義的（相當于求兩個正數的最大公倍數）。

原文鏈接：https://blog.csdn.net/weixin_43772810/article/details/122064989

欄目分類
最近更新