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

 更新时间:2021-12-22 15:59:54   作者:佚名   我要评论(0)

目录题目描述问题分析方法一:穷举法方法二:定理法题目描述
求任意两个正整数的最小公倍数
问题分析
两个或多个整数公有的倍数叫做它们的公

题目描述

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

问题分析

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

运行结果

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

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

您可能感兴趣的文章:
  • 详解C语言求两个数的最大公约数及最小公倍数的方法
  • Python 代码实现列表的最小公倍数
  • python求最大公约数和最小公倍数的简单方法
  • Python基于递归算法求最小公倍数和最大公约数示例
  • java求最大公约数与最小公倍数的方法示例
  • C++ 实现求最大公约数和最小公倍数
  • C#获取两个数的最大公约数和最小公倍数示例

相关文章

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

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

    目录题目描述问题分析方法一:穷举法方法二:定理法题目描述 求任意两个正整数的最小公倍数 问题分析 两个或多个整数公有的倍数叫做它们的公
    2021-12-22
  • .NET中IoC框架Autofac用法讲解

    .NET中IoC框架Autofac用法讲解

    1 前置阅读 在阅读本文章之前,你可以先阅读: 什么是依赖注入 2 简介 Autofac与C#语言的结合非常紧密,并学习它非常的简单,也是.NET
    2021-12-22
  • Vue lazyload图片懒加载实例详解

    Vue lazyload图片懒加载实例详解

    文档:https://github.com/hilongjw/vue-lazyload 1.安装 cnpm i vue-lazyload -S 或 npm i vue-lazyload -S 2.实例 导入配置等操作 src/
    2021-12-22
  • 用Docker搭建nextcloud个人网盘教程

    用Docker搭建nextcloud个人网盘教程

    目录一、简介二、部署环境三、工具四、部署过程总结一、简介 nextcloud是一个非常好用的网盘系统,功能强大插件齐全,非常适用于个人网盘和企
    2021-12-22
  • 基于Python实现人像雪景小程序

    基于Python实现人像雪景小程序

    目录导语?正文1)素材环境(仅部分)2)运行环境3)代码演示4)效果展示导语 哈喽~大家早上好鸭! 冷空气来袭,不少地方一夜入冬,南方地区除了
    2021-12-22
  • Python的Scrapy框架解析

    Python的Scrapy框架解析

    目录一.为什么使用Scrapy框架&#63;二.Scrapy框架每个组件介绍三.Scrapy框架工作原理总结一.为什么使用Scrapy框架&#63; Scrapy是一个快速、高
    2021-12-22
  • python数据分析之文件读取详解

    python数据分析之文件读取详解

    目录前言:一·Numpy库中操作文件二·Pandas库中操作文件三·补充总结前言: 如果你使用的是Anaconda中的Jupyter,则不需要下载Pands和Numpy
    2021-12-22
  • C语言实现求最大公约数的三种方法

    C语言实现求最大公约数的三种方法

    目录题目描述问题分析代码实现方法一:穷举法方法二:辗转相除法方法三:更相减损法题目描述 求任意两个正整数的最大公约数 问题分析 最大公
    2021-12-22
  • 使用Log4j2代码方式配置实现线程级动态控制

    使用Log4j2代码方式配置实现线程级动态控制

    目录一 需求二 对外暴露的接口三 代码方式配置Log4j2日志对象四 线程级日志对象的设计五 标准日志头六 异常日志的堆栈信息打印七 测试一 需求
    2021-12-22
  • 浅谈Django Admin的初步使用

    浅谈Django Admin的初步使用

    目录创建管理员用户更改admin后台语言应用后端管理功能完善设置模型名设置显示的字段后端管理系统名称创建管理员用户 命令行输入python mana
    2021-12-22

最新评论