最小公倍数=两数乘积/最大公约数
求最小公约数可以使用欧得几里算法（也就是传说中的辗转相除法）
int gcd(int a,int b)
{
if(b==0)
return a;
return
gcd(b,a%b);
}【C++ 实现最小公倍数】 也可以使用(这两个方法的原理都是一样的)
int gcd(int x,int y)
{
while(x!=y)
{if(x>y) x=x-y;
else
y=y-x;
}
return x;
//辗转相除法
}
有时候两数乘积会超过整数的范围,由此我们可以调整一下顺序:a/gcd(a,b)*b
先除一下，这样就可以避免在一定程度上避免溢出
#include
#include
#include
#include
using namespace std;
int gcd(int,int);
int main(int argc,char *argv[])
{
int x,y;
while(cin>>x>>y)
{
cout<y) x=x-y;
else
y=y-x;
}
return x;
//辗转相除法
}
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔