[算法]欧几里得算法（辗转相除法和更相减损法求最大公约数和最小公倍数）

一.更相减损法

代码（C++描述）：

(局限性：x，y都为正数时才可用)

 1 /**更相减损法求最大公因数和最小公倍数*/ 
 2 #include<iostream>
 3 using namespace std;
 4 int main(){
 5     int x,y,n,m;
 6     cin>>x>>y;
 7     n=x,m=y;
 8     while(x!=y){
 9         x>y?x=x-y:y=y-x; 
10     }
11     cout<<"最大公因数为："<<x<<endl;
12     cout<<"最小公倍数为："<<(n/x)*(m/x)*x;
13     return 0;
14 }

二.辗转相除法

代码（C++描述）：

 1 /**辗转相除法求最大公因数和最小公倍数*/
 2 #include<iostream>
 3 using namespace std;
 4 int main(){
 5     int x,y,n,m;
 6     cin>>x>>y;
 7     n=x,m=y;
 8     int r;
 9     while(y!=0){
10         r=x%y;
11         x=y,y=r;
12     }
13     cout<<"最大公因数为："<<x<<endl;
14     cout<<"最小公倍数为："<<(n/x)*(m/x)*x;
15     return 0;
16 }