【笔试题】求最小公倍数 C++(两种方法)
2021/5/5 22:25:22
本文主要是介绍【笔试题】求最小公倍数 C++(两种方法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
本题链接:求最小公倍数
正整数A和正整数B 的最小公倍数是指能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。
输入描述:
输出描述:
示例1:
解题思路一: 暴力破解
从两个数中较大的数开始,逐个进行判断,能够被两个数整除,则第一个就是最小公倍数。
代码:
#include<iostream> using namespace std; int main() { int a, b; while(cin >> a >> b) { int m = max(a, b);//a,b中的较大值 while(1) { if(m % a == 0 && m % b == 0) { cout << m <<endl; break; } m++;//从较大的数开始,一个数一个数往后判断 } } return 0; }
暴力求解的效率太低,需要另一种方法来求解问题。
解题思路二: 更优方法
最小公倍数 = 两数之积除以最大公约数,在这里使用辗转相除的方法求解最大公约数,即a与b的最大公约数可以转化为a、b之间的余数为两者之间最小的数之间的公约数。所以对于输入的两个数进行连续求余,直到余数为0,求余的分母即为结果。
辗转相除法求最大公约数举例:25 15求最大公约数
25 % 15 = 10,10不等于0,继续取余
15 % 10 = 5,5 等于0,继续取余
10 % 5 = 0,所以求得最大公约数5
代码:
#include<iostream> using namespace std; //求最大公约数 int gcb(int a, int b) { int c = 0; while(c = a % b) { a = b; b = c; } return b; } int main() { int a, b; while(cin >> a >> b) { //最小公倍数 = 两数之积除以最大公约数 cout << a * b / gcb(a, b) << endl; } return 0; }
这篇关于【笔试题】求最小公倍数 C++(两种方法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享