公约数
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
main() { int p,r,n,m,temp; printf("Please enter 2 numbers n,m:"); scanf("%d,%d",&n,&m);//输入两个正整数. if(n把大数放在n中,把小数放在m中. {temp=n; n=m; m=temp; }
p=n*m;//P是原来两个数n,m的乘积.
while(m!=0)//求两个数n,m的最大公约数. {
r=n%m; n=m; m=r; }
printf("Its MAXGongYueShu:%d\n",n);//打印最大公约数. printf("Its MINGongBeiShu:%d\n",p/n);打印最小公倍数. 基本原理如下：
用欧几里德算法（辗转相除法）求两个数的最大公约数的步骤如下： 先用小的一个数除大的一个数，得第一个余数； 再用第一个余数除小的一个数，得第二个余数； 又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。 例如求1515和600的最大公约数， 第一次：用600除1515，商2余315； 第二次：用315除600，商1余285； 第三次：用285除315，商1余30； 第四次：用30除285，商9余15； 第五次：用15除30，商2余0。 1515和600的最大公约数是15。
两个正整数的最小公倍数=两个数的乘积÷两个数的最大公约数 由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。这就是说，求两个数的最小公倍数，可以先求出两个数的最大公约数，再用这两个数的最大公约数去除这两个数的积，所得的商就是两个数的最小公倍数。 例求105和42的最小公倍数。
因为105和42的最大公约数是21，
105和42的积是4410，4410÷21＝210， 所以，105和42的最小公倍数是210
本文来源：https://www.wddqw.com/doc/6fda45d509a1284ac850ad02de80d4d8d15a014e.html