分条整经机条宽的算法

 分条整经机条宽的算法

scanf(;%d,%d;,n,m);//输入两个正整数.

if(nlt;m)//把大数放在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。