辗转相除法用于求最大公倍数和最小公约数。首先我讲讲怎么算：现在有两个数，12和18，其中较大数是18，那么用18对12取余数，得到6，再用12对6取余数，发现可以整除，于是最大公约数就是6。这个过程对于人来说显得较为复杂，毕竟这明明是一个能一眼看出结果的问题，但是这个过程对于计算机来说，确实很容易的，并且此过程很显然适合用编程来实现。下面讲讲原理，假设12和18的最大公约数是x，那么可得12/x=a，18/x=b，a和b肯定都是整数，而且b＞a，两式想减6=(b-a)x，b-a肯定也是个整数，所以6也可以被x整除。此时需要注意，我们的目标就是求出x，由于6也可以被整x整除，所以这个问题转换为了求6、12的最大公约数，所以可以对这两个数再进行相同操作（注意，可重复操作，所以适合用循环语句来实现）。最后即可得到最大公约数。最大公倍数只需要用12*18/6即可得到，此处为小学或初中内容了，无需多言。
发布评论
代码已上传![[s-7]](https://resource.mfuns.net/image/sticker/s/7.png)
//辗转相除法求最小公倍数
#if 0
#include<iostream>
using namespace std;
int main(){
int a = 0, b = 0;
while(cin>>a>>b){
int max = a,min=b;
if(a<b){
max = b;
min = a;
}
while (max % min != 0){
int temp = min;
min = max % min;
max = temp;
}
cout << a*b/min<<endl;
}
return 0;
}
#endif
等等我好像忘了贴上代码。。。明天放到评论区吧。