Question

求两个数字的最大公倍数和最小公约数的算法是怎么样的?

Answer 1

如果是你敲错了字（不是脑筋急转弯）的话,

求两个数字的最大公约数和最小公倍数的方法：

可以先用辗转相除法求出这两个数的最大公约数,

再用这两个数的乘积除以它们的最大公约数,就得到它们的最小公倍数.

用计算机C语言实现的程序如下：

设两个整数为u和v,用辗转相除法求最大公约数的算法.最小公倍数=uv/最大公约数.

程序如下：

#include

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=%dn",h);

l=lcd(u,v,h);

printf("L.C.D=%dn",l);

}

运行结果如下：

24,16↙

H.C.F=8

L.C.D=48