分條整經(jīng)機(jī)條寬的算法

scanf(;%d,%d;,n,m);//輸入兩個正整數(shù).

if(nlt;m)//把大數(shù)放在n中,把小數(shù)放在m中.

{temp=n;

n=m;

m=temp;

}

p=n*m;//P是原來兩個數(shù)n,m的乘積.

while(m!=0)//求兩個數(shù)n,m的公約數(shù).

{

r=n%m;

n=m;

m=r;

}

printf(;Its MAXGongYueShu:%d;n;,n);//打印公約數(shù).

printf(;Its MINGongBeiShu:%d;n;,p/n);打印公倍數(shù).

分批整經(jīng)機(jī)

基本原理如下：

用歐幾里德算法（輾轉(zhuǎn)相除法）求兩個數(shù)的公約數(shù)的步驟如下：

先用小的數(shù)除大的一個數(shù)，得余數(shù)；

再用余數(shù)除小的一個數(shù)，得余數(shù)；

又用余數(shù)除余數(shù)，得余數(shù)；

這樣逐次用后一個數(shù)去除前一個余數(shù)，直到余數(shù)是0為止。那么，一個除數(shù)就是所求的公約數(shù)（如果的除數(shù)是1，那么原來的兩個數(shù)是互質(zhì)數(shù)）。

例如求1515和600的公約數(shù)，

一：用600除1515，商2余315；

二：用315除600，商1余285；

三：用285除315，商1余30；

四：用30除285，商9余15；

五：用15除30，商2余0。

1515和600的公約數(shù)是15。

兩個正整數(shù)的公倍數(shù)=兩個數(shù)的乘積÷兩個數(shù)的公約數(shù)

由于兩個數(shù)的乘積等于這兩個數(shù)的公約數(shù)與公倍數(shù)的積。這就是說，求兩個數(shù)的公倍數(shù)，可以先求出兩個數(shù)的公約數(shù)，再用這兩個數(shù)的公約數(shù)去除這兩個數(shù)的積，所得的商就是兩個數(shù)的公倍數(shù)。

例 求105和42的公倍數(shù)。

因為105和42的公約數(shù)是21，

105和42的積是4410，4410÷21＝210，

所以，105和42的公倍數(shù)是210。