最小公倍数问题

作者：fighter19 来源：不详发布时间：2008/08/01 发布人：admin

fighter19 发布留言 2008-7-31 21:37

最小公倍数问题

不用最大公约数的情况下怎样求两个数的最小公倍数？算法思想是怎样的？

谢谢帮忙！

AriesZ 发布留言 2008-7-31 21:56

#include
#include
main(void)
{
int gcd(int,int),lcm(int,int),n,m;
int a,b;
scanf("%d%d",&a,&b);
n=gcd(a,b);
m=lcm(a,b);
printf("gcd=%d,lcm=%d",n,m);
}
int gcd(int x,int y)
{
int i,k;
if (x>y) k=y;
else k=x;
for (i=k;i>0;i--)
{if (x%i==0&&y%i==0) return i;}
}
int lcm(int x,int y)
{
int i,j,k;
if (x>y) k=x;
else k=y;
for (i=k;i<=k*k;i++)
{if (i%x==0&&i%y==0) return i;}
}
现编的，最大公倍数和最大公约数都有了，楼主自己看看～～
用了两函数,lcm()那个是最小公倍数。

woshiyun 发布留言 2008-7-31 22:14

2#，你的效率都太低了，帮你改一改公倍数的，公约数自己去看辗转相除吧

int lcm(int x,int y)
{
if (x>y) x^=y^=x^=y;
for (int i=y;;i+=y)
{if(i%x==0) return i;}
}

fighter19 发布留言 2008-7-31 22:24

回复 3# woshiyun 的帖子

3Q very much!

AriesZ 发布留言 2008-7-31 22:34

回复 3# woshiyun 的帖子

谢谢啦～其实我就学了那么多的。。。

页: [1]

特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！

[] [返回] [打印] [收藏] [评论]

上一篇代码：【讨论】如何返回两个数中较大的数

下一篇代码：【求助】WIN32学的好的近（不要谦虚）

最小公倍数问题