C++求最小公倍数

时间:2024-07-19 14:33:08

题目内容:求两个正整数的最小公倍数。

输入描述:输入数据含有不多于50对的数据,每对数据由两个正整数(0<n1,n2<100000)组成。

输出描述:对于每组数据n1和n2,计算最小公倍数,每个计算结果应单独占一行。

题目分析:对于32位CPU,int的表示范围为-231~0~(+231-1),即-2147483648~2147483647有符号数,用最高位表示符号(1正0负)。

最小公倍数=X*Y/gcd(x,y);但两数先乘会产生很大的数,可能会超过整数的表示范围,所以,把计算顺序修改一下就可以了:最小公倍数=X/gcd(x,y)*Y。

参考代码:

#include <iostream>
#include <fstream> using namespace std;
int gcd(int,int);
int main(int argc,char * argv[])
{
int x,y;
while(cin>>x>>y)
{
cout<<x/gcd(x,y)*y<<endl;
}
system("pause");
return 0;
}
int gcd(int x,int y)
{
while(x!=y)
{
if(x>y) x=x-y;
else
y=y-x;
}
return x;
}

效果如图:

C++求最小公倍数