当前位置:网站首页>C语言每日一练——Day02:求最小公倍数(3种方法)
C语言每日一练——Day02:求最小公倍数(3种方法)
2022-08-11 06:06:00 【小牛要翻身】
一、什么是公倍数?
通过直观的理解,我们很容易知道,所谓的公倍数就是两个数共有的倍数;那么最小公倍数,就是他们共有的倍数中最小的那个数。比如2和4的最小公倍数是4,15和20的最小公倍数是60……
二、求解两个数的最小公倍数
1、枚举法
思路: 已知两个数的最小公倍数大于等于两个数的最大值,所以可以先求出两个数的较大值
max
,用max分别试除两个数,如果能整除,max即为两个数的最小公倍数;不能整除,让max=max+1
直到找到最小公倍数为止。
️如:求12和8的最小公倍数
- 先求较大值12,12不是两个数的最小公倍数
- 12+1=13,13+1=14……,23+1=24可以整除这两个数
- 所以24是最小公倍数
代码展示:
//枚举法
#include<stdio.h>
int main()
{
int x = 0;
int y = 0;
scanf("%d %d",&x,&y);
int max = (x > y ? x : y);//取最大值
while (max%x != 0 || max%y!= 0)//如果不能同时整除
{
max++;//每次增加1
}
printf("%d",max);
return 0;
}
2、公式法
思路: 两个数的最小公倍数数等于两个数的乘积除以两个数的最大公约数。即:x,y的最小公倍数
min(公倍数)=x*y÷max(公约数)
️如:求12和8的最小公倍数
- 求得12和8的最大公约数是4
- 即12和8的最小公倍数是12×8÷4=24
代码展示:
//公式法:
#include<stdio.h>
int main()
{
int x = 0;
int y = 0;
scanf("%d %d",&x,&y);
int z = x * y;//将两个数的乘积存起来方便后续使用
//求最大公约数
while (x % y != 0)
{
int tmp = x % y;
x = y;
y = tmp;
}
int min = z / y;//最小公倍数
printf("%d",min);
return 0;
}
3、迭乘法
思路: 已知两个数的公倍数一定与这两个数存在倍数关系,那么求解最小公倍数我们就可以将其中一个数依次扩大
1
倍、2
倍、3
倍……直到出现第一个扩大n
倍的数可以同时整除这两个数,这个数就是最小公倍数。
️如:求12和8的最小公倍数
- 12×1=12,12不是8的倍数
- 12×2=24,24是8的倍数
- 24是12和8的最小公倍数
代码展示:
//迭乘法
#include<stdio.h>
int main()
{
int x = 0;
int y = 0;
scanf("%d %d",&x,&y);
int i = 1;
while (x * i %y != 0)
{
i++;
}
printf("%d",x*i);
return 0;
}
总结
上述三种方法中:
- 迭乘法效率最高,建议使用。
- 枚举法效率最低,不推荐使用。
边栏推荐
- 拼多多API接口(附上我的可用API)
- 每日sql -查询至少有5名下属的经理和选举
- HCIA knowledge review
- Trill keyword search goods - API
- Class definition, class inheritance, and the use of super
- How to choose professional, safe and high-performance remote control software
- 抖音API接口大全
- JVM学习——3——数据一致性
- 技能在赛题解析:交换机防环路设置
- Redis + lua implements distributed interface current limiting implementation scheme
猜你喜欢
随机推荐
ROS 话题通信理论模型
一种用于EEG超扫描研究的分析流程
Redis + lua implements distributed interface current limiting implementation scheme
Concurrent programming in eight-part essay
[损失函数]——均方差
《猪猪1984》NFT 作品集将上线 The Sandbox 市场平台
unable to extend table xxx by 1024 in tablespace xxxx
Daily sql - judgment + aggregation
求过去半年内连续30天以上每天都有1000元以上成交的商铺
一个小时快速熟悉MySQL基本用法
Taobao sku API interface (PHP example)
你是如何做好Unity项目性能优化的
When MySQL uses GROUP BY to group the query, the SELECT query field contains non-grouping fields
2022-08-09 第四小组 修身课 学习笔记(every day)
SQL sliding window
Daily sql--statistics the total salary of employees in the past three months (excluding the latest month)
HCIP OSPF dynamic routing protocol
【深度学习】什么是互信息最大化?
拼多多API接口大全
Strongly recommend an easy-to-use API interface