C趣味程序(二)(07)求多个整数的最大公约数与最小公倍数

文章作者 100test 发表时间 2007:03:10 17:39:23
来源 100Test.Com百考试题网

2.1.2 求多个整数的最大公约数与最小公倍数
对于3个或3个以上整数，最大公约数与最小公倍数有以下性质：
(a1,a2,a3)=((a1,a2),a3)
(a1,a2,a3,a4)=((a1,a2,a3),a4),...
{a1,a2,a3}={{a1,a2},a3}
{a1,a2,a3,a4}={{a1,a2,a3},a4},...
应用这一性质，要求n个数的最大公约数，先求出前n-1个数的最大公约数t,再求第n个数与t的最大公约数。求n个数的最小公倍数也一样。这样递推实现求多个整数的最大公约数与最小公倍数。
程序代码如下：
#include
int gy(int,int).
int gb(int,int).
void main()
{
int a,b,c,d,i=2.
int aa[10].
printf("n个整数的最大公约记为(a1,a2,...an)\n").
printf("n个整数的最小公倍记为{a1,a2,...an}\n").
printf("n个整数逐个从键盘输入，以-1终止\n").
printf("首先输入两个数a,b\n").
scanf("%d,%d",&.a,&.b).
c=a.
d=a.
aa[0]=a.aa[1]=b.
while(b>0)
{
c=gy(c,b). /*调用最大公约数函数*/
d=gb(d,b). /*调用最小公倍数函数*/
printf("输入下一个整数(输入-1结束)：to b: ").
scanf("%d",&.b).
aa[i]=b.
i .
}
printf("(").
for(i=0.aa[i]!=-1.i )
printf("%d,",aa[i]).
printf(") = %d\n",c).
printf("{").
for(i=0.aa[i]!=-1.i )
printf("%d,",aa[i]).
printf("} = %d\n",d).
}
int gy(int x,int y)
{
int c.
for(c=x.c>=1.c--)
{
if((x/c==(float)x/c)&.&.(y/c==(float)y/c))
break.
}
return c.
}
int gb(int x,int y)
{
int d.
for(d=x. d<=x*y.d =x)
{
if(d/y==(float)d/y) break.
}
return d.
}
程序运行结果如下：

说明：
对n(n>=3)个整数，不存在最大公约与最小公倍的积等于这n个整数之积的性质。因此不能套用2个整数的性质，以防出错。