求三个数的最大公约数及最小公倍数

欢迎大家来到IT世界,在知识的湖畔探索吧!

三个正整数a,b,c的最大公约数为p，记作：(a,b,c)=p；最小公倍数为q，记作：[a,b,c]=q.

例.求18,24,36的最大公约数及最小公倍数。

解法一、用短除法:

欢迎大家来到IT世界,在知识的湖畔探索吧!

1）求最大公约数：

1. 先用18,24,36的公因数2去除：18除以2得9，24除以2得12,36除以2得18,三个数成为：9,12,18.
2. 再用9,12,18的公因数3去除：9除以3得3,12除以3得4,18除以3的6，三个数成为：3,4,6.此时3,4,6再没有大于1的公因数。所以，18,24,36的最大公约数为：2*3=6.即(18,24,36)=6.

2）求最小公倍数：

接着上面对3,4,6继续用短除法：

1. 用4和6的公因数2去除：3不能被2整除挪下来，4除以2得2，6除以2得3，三个数成为：3,2,3.
2. 再用3和3的公因数3去除：3除以3得1，2不能被3整除挪下来，3除以3得1，三个数成为：1,2,1.此时它们两两都没有大于1的公因数啦，短除法结束。
3. 把所有公因数(包括三个数的公因数2,3，两个数的公因数2,3)以及最后的商1,2,1相乘：2*3*2*3*1*2*1=72.得到18,24,36的最小公倍数为：[18,24,36]=72.

解法二、先求出其中两个数的最大公约数p和最小公倍数q，再求p与第三个数的最大公约数，以及q与第三个数的最小公倍数：

1)求最大公约数：因为(18,24)=6,又因为(6,36)=6，所以(18,24,36)=6.

2)求最小公倍数：因为[18,24]=72,又因为[72,36]=72，所以[18,24,36]=72

用C语言编程如下：

//求三个数a,b,c的最大公约数p及最小公倍数q，记作：p=(a,b,c)，q=[a,b,c]

#include <stdio.h>

int main ()

{ int gys(int,int); //函数原型：求最大公约数

int a,b,c,p,q;

printf(“请输入三个整数:a b c(相互用空格隔开)：”); scanf(“%d %d %d”,&a,&b,&c);

p=gys(a,b);//调用函数:求a,b的最大公约数p

q=a*b/p; //求a,b的最小公倍数q(注：因两个数a,b的最大公约数p与它们的最小公倍数q之积pq,等于这两个数之积ab)

p=gys(p,c);//求p,c的最大公约数(也即a,b,c的最大公约数)仍用p表示

printf(“(%d,%d,%d)=%d, “,a,b,c,p); //输出三个数的最大公约数

p=gys(q,c);//求q,c的最大公约数p

printf(” [%d,%d,%d]=%d”,a,b,c,q*c/p); //输出三个数的最小公倍数

}

//求最大公约数函数：

int gys(int x,int y) //x,y为形参

{ int r=1;//使循环能进行

while(r!=0) //辗转相除：

{ r=x%y;//求余

x=y;y=r;//辗转

}

return (x); //返回最大公约数x

}