C语言实现求解最小公倍数的算法示例

题目描述

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

问题分析

两个或多个整数公有的倍数叫做它们的公倍数，其中除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;
}

运行结果

方法二：定理法

使用定理求最小公倍数（两个整数的最小公倍数等于两数之积除以两个数的最大公因数），需要先求出两个整数的最大公因数，最大公因数这里采用辗转相除法。（最大公因数的求法可以参考我上一篇文章——）

【不考虑负数，求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）】

#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;
}

运行结果

如果程序不作处理（不检测输入的数字是否为正数），此时输入负数，也能返回一个公倍数，但不是“最小”公倍数，不过求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）。

到此这篇关于c语言实现求解最小公倍数的算法示例的文章就介绍到这了,更多相关c语言求解最小公倍数内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！