[C++知识库]3 求最大公约数和最小公倍数

题目描述

输入两个整数，求两个整数的最大公约数和最小公倍数，并输出结果。

设两个整数为u和v，用辗转相除法求最大公约数和最小公倍数的算法如下：

if v>u

?? 将变量u与v交换???????????? （使大者u为被除数）

while (u/v的余数r!=0)

?? {u=v????????????????????????????? （使除数v变为被除数u）

???? v=r????????????????????????????? （使余数r变为除数v）

}

输出最大公约数v(目前）

最小公倍数l＝u*v（原来）/最大公约数v

样例输入

36 12

样例输出

最大公约数：12
最小公倍数：36

代码

#include <iostream>
using namespace std;
int max(int m,int n)
{int t,r,max;
 if(n>m)
  {t=n;n=m;m=t;}
  r=m%n;
  while(r!=0)
  {m=n;n=r;r=m%n;}
  max=n;
  return max;
}
int min(int m,int n,int c)
{int min;
 min=m*n/c;
 return min;
}
int main()
{ int m,n,x,y;
  cin>>m>>n;
  x=max(m,n);
  y=min(m,n,x);
  cout<<"最大公约数："<<x<<endl;
  cout<<"最小公倍数："<<y<<endl;
  return 0;
}