求两个数的最大公约数及最小公倍数求两个数的最大公约数和最小公倍数 _小知识

两个正整数a,b的最大公约数为p ，记作：(a,b)=p；最小公倍数为q ，记作：[a,b]=q.
例1.求24和30的最大公约数及最小公倍数。
解：对于比较简单的数，可以直接观察出它们的公因数，适合用短除法：
1）先用24和30的公因数2分别去除两个数24,30 ，得商12和15；
2）再用12和15的公因数3分别去除12,15 ，得商4和5；
3） 4和5已经没有比1大的公因数了，短除法结束。

文章插图
因为两个公因数2和3 之积为：2*3=6 ，所以24和30的最大公约数为：(24,30)=6 。
又因为所有公因数以及最后的商之积为：2*3*4*5=120 ，
所以24和30的最小公倍数为：[24,30] =120 。
例2.求221和493的最大公约数及最小公倍数。
解：对于不易观察出公因数的数，可以用辗转相除法：

用较大的数除以较小的数并求出余数得：493/221=2 ，余数为51；
把上面的除数作为被除数，余数作为除数，再求余数得：221/51=4 ，余数为17；
再把上面的除数作为被除数，余数作为除数，求余数得：51/17=3 ，余数为0.

【求两个数的最大公约数及最小公倍数求两个数的最大公约数和最小公倍数】当余数为0时，倒数第二个余数就是这两个数的最大公约数。所以， 221和493的最大公约数为：(221,493)=17 。
又因为两个数a,b的最大公约数p与最小公倍数q之积pq ，等于这两个数之积ab 。所以q=(ab)/p.
所以， 221余493的最小公倍数为：[221,493]=221*493/17=6409.
用C语言编程如下：
//求两个数a,b的最大公约数p及最小公倍数q
#include <stdio.h>
int main () //注：两个数的最大公约数与最小公倍数之积=这两个数的乘积，即pq=ab ，所以q=ab/p
{ int gys(int,int); //函数原型：求最大公约数
int a,b,p;
printf("请输入两个整数:a b（两数用空格隔开）："); scanf("%d %d",&a,&b);
p=gys(a,b);//调用函数求a,b的最大公约数P
printf("(%d,%d)=%d ， ",a,b,p); //输出最大公约数
printf("[%d,%d]=%d",a,b,a*b/p); //输出最小公倍数(因pq=ab,所以q=ab/p)
}
//求最大公约数函数：
int gys(int x,int y) //函数首部行 ,这里x,y为形式参数
{ int r=1;//使r不为0
while(r!=0) //辗转相除：
{ r=x%y;//求余
x=y;y=r;//辗转
}
return (x); //返回最大公约数x
}

求两个数的最大公约数及最小公倍数 求两个数的最大公约数和最小公倍数

求两个数的最大公约数及最小公倍数求两个数的最大公约数和最小公倍数