已知m,n均为正整数，试用C语言写出求m与n的最小公倍数的算法，算法的步骤为：
（1） 计算m*n的积，送临时变量r。
（2） 若m等于n，则输出最小公倍数r/m，算法结束。
（3） 若m大于n，计算m-n，结果送m，否则，计算n-m，结果送n。
（4） 转到（2）或者（3）。
（1）分解质因数法
先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。
比如求45和30的最小公倍数。
45=3*3*5
30=2*3*5
不同的质因数是2,3,5。3是他们两者都有的质因数，由于45有两个3，30只有一个3，所以计算最小公倍数的时候乘两个3.
最小公倍数等于2*3*3*5=90
又如计算36和270的最小公倍数
36=2*2*3*3
270=2*3*3*3*5
不同的质因数是5。2这个质因数在36中比较多，为两个，所以乘两次；3这个质因数在270个比较多，为三个，所以乘三次。
最小公倍数等于2*2*3*3*3*5=540
20和40的最小公倍数是40
（2）公式法
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
例如，求[18，20]，即得[18，20]=18×20÷（18，20）=18×20÷2=180。求几个自然数的最小公倍数，可以先求出其中两个数的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数，依次求下去，直到最后一个为止。最后所得的那个最小公倍数，就是所求的几个数的最小公倍数。
先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。
比如求45和30的最小公倍数。
45=3*3*5
30=2*3*5
不同的质因数是2,3,5。3是他们两者都有的质因数，由于45有两个3，30只有一个3，所以计算最小公倍数的时候乘两个3.
最小公倍数等于2*3*3*5=90
又如计算36和270的最小公倍数
36=2*2*3*3
270=2*3*3*3*5
不同的质因数是5。2这个质因数在36中比较多，为两个，所以乘两次；3这个质因数在270个比较多，为三个，所以乘三次。
最小公倍数等于2*2*3*3*3*5=540
20和40的最小公倍数是40
（2）公式法
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
例如，求[18，20]，即得[18，20]=18×20÷（18，20）=18×20÷2=180。求几个自然数的最小公倍数，可以先求出其中两个数的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数，依次求下去，直到最后一个为止。最后所得的那个最小公倍数，就是所求的几个数的最小公倍数。
温馨提示：答案为网友推荐，仅供参考
第1个回答 2006-09-19
设两个整数为u和v，用辗转相除法求最大公约数的算法。最小公倍数=uv/最大公约数。
程序如下：
#include <stdio.h>
int hcf(int u,int v)
{ int t,r;
if(v>u)
{ t=u;u=v;v=t;}
while((r=u%v)!=0)
{ u=v;
v=r;
}
return(v);
}
int lcd(int u,int v,int h)
{
return(u*v/h);
}
main( )
{ int u,v,h,l;
scanf("%d,%d",&u,&v);
h=hcf(u,v);
printf("H.C.F=%d\n",h);
l=lcd(u,v,h);
printf("L.C.D=%d\n",l);
}
程序如下：
#include <stdio.h>
int hcf(int u,int v)
{ int t,r;
if(v>u)
{ t=u;u=v;v=t;}
while((r=u%v)!=0)
{ u=v;
v=r;
}
return(v);
}
int lcd(int u,int v,int h)
{
return(u*v/h);
}
main( )
{ int u,v,h,l;
scanf("%d,%d",&u,&v);
h=hcf(u,v);
printf("H.C.F=%d\n",h);
l=lcd(u,v,h);
printf("L.C.D=%d\n",l);
}
第2个回答 2019-03-11
两个数相乘一定是它们的公倍数.但不是最小公倍数.因为,它们相同的公因数乘了两次.而这些相同公因数都是它们的约数.其乘积就是最大因约数.也就是说,最大公约数乘了两次.所以要除去一次.比如8和12.
8=2*2*2
12=2*2*3
最小公倍数应该是2*2*2*3=24相同的只取一次的.
如果直接两数相乘就不是取一次了.而是取了几倍次.不是吗?对比一下8*12=2*2*2*2*2*3
是不是多了2*2?这正是8和12的最大公约数嘛.
8=2*2*2
12=2*2*3
最小公倍数应该是2*2*2*3=24相同的只取一次的.
如果直接两数相乘就不是取一次了.而是取了几倍次.不是吗?对比一下8*12=2*2*2*2*2*3
是不是多了2*2?这正是8和12的最大公约数嘛.
第3个回答 2020-04-06
1.（分解要彻底，一定全是质数）
9=3*3*1
5=5*1
4=2*2*1
最大公约数就是找上面几式中同时出现的数
9，5，4的最大公约数是1
9，5，4的最小公倍数是3*3*5*2*2*1=180
2。
5=5*1
6=1*2*3
7=7*1
5,6,7的最大公约数是1
5,6,7的最小公倍数是3*2*5*7*1=210
3.
5=5*1
9=3*3*1
12=3*2*2*1
5,9,12的最大公约数是1
5,9,12的最小公倍数是3*3*1*5*2*2=180
4。
6=2*3*1
12=2*2*3*1
18=2*3*3*1
30=2*3*5*1
6，12，18，30的最大公约数是3*2=6
6，12，18，30的最小公倍数是3*2*1*2*3*5=180
9=3*3*1
5=5*1
4=2*2*1
最大公约数就是找上面几式中同时出现的数
9，5，4的最大公约数是1
9，5，4的最小公倍数是3*3*5*2*2*1=180
2。
5=5*1
6=1*2*3
7=7*1
5,6,7的最大公约数是1
5,6,7的最小公倍数是3*2*5*7*1=210
3.
5=5*1
9=3*3*1
12=3*2*2*1
5,9,12的最大公约数是1
5,9,12的最小公倍数是3*3*1*5*2*2=180
4。
6=2*3*1
12=2*2*3*1
18=2*3*3*1
30=2*3*5*1
6，12，18，30的最大公约数是3*2=6
6，12，18，30的最小公倍数是3*2*1*2*3*5=180
第4个回答 2006-09-19
main(){
int m,n;
scanf("%d",m);
scanf("%d",n);
int r=m*n;
if(m==n)
printf("",r/m);
else if(m>n){
m=m-n;
}
else{
n=n-m;
}
}本回答被提问者采纳
int m,n;
scanf("%d",m);
scanf("%d",n);
int r=m*n;
if(m==n)
printf("",r/m);
else if(m>n){
m=m-n;
}
else{
n=n-m;
}
}本回答被提问者采纳
