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<stdio.h>
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个整数的性质，以防出错。
责任编辑：cyth
