求最大公約數(shù)九法

湖南省武岡市教研室 周定武

　　一、觀察法．

　　運用能被2、3、5整除的數(shù)的特征進行觀察．

　　例如，求225和105的最大公約數(shù)．因為225、105都能被3和5整除，所以225和105至少含有公約數(shù)（3×5）15．因為225÷15＝15，105÷15＝7．15與7互質(zhì)，所以225和105的最大公約數(shù)是15．

　　二、查找約數(shù)法．
先分別找出每個數(shù)的所有約數(shù)，再從兩個數(shù)的約數(shù)中找出公有的約數(shù)，其中最大的一個就是最大公約數(shù)．

　　例如，求12和30的最大公約數(shù)．
12的約數(shù)有：1、2、3、4、6、12；
30的約數(shù)有：1、2、3、5、6、10、15、30．
12和30的公約數(shù)有：1、2、3、6，其中6就是12和30的最大公約數(shù)．

　　三、分解因式法．

　　先分別把兩個數(shù)分解質(zhì)因數(shù)，再找出它們?nèi)抗械馁|(zhì)因數(shù)，然后把這些公有質(zhì)因數(shù)相乘，得到的積就是這兩個數(shù)的最大公約數(shù)．

　　例如：求125和300的最大公約數(shù)．因為125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公約數(shù)是5×5＝25．

　　四、關(guān)系判斷法．

　　當兩個數(shù)關(guān)系特殊時，可直接判斷兩個數(shù)的最大公約數(shù)．例如，兩個數(shù)互質(zhì)時，它們的最大公約數(shù)就是這兩個數(shù)的乘積；兩個數(shù)成倍數(shù)關(guān)系時，它們的最大公約數(shù)就是其中較小的那個數(shù)．

　　五、短除法．

　　為了簡便，將兩個數(shù)的分解過程用同一個短除法來表示，那么最大公約數(shù)就是所有除數(shù)的乘積．

　　例如：求180和324的最大公約數(shù)．

　　因為：

　　5和9互質(zhì)，所以180和324的最大公約數(shù)是4×9＝36．

　　六、除法法．

　　當兩個數(shù)中較小的數(shù)是質(zhì)數(shù)時，可采用除法求解．即用較大的數(shù)除以較小的數(shù)，如果能夠整除，則較小的數(shù)是這兩個數(shù)的最大公約數(shù)．

　　例如：求19和152，13和273的最大公約數(shù)．因為152÷19＝8，273÷13＝21．（19和13都是質(zhì)數(shù)．）所以19和152的最大公約數(shù)是19，13和273的最大公約數(shù)是13．

　　七、縮倍法．

　　如果兩個數(shù)沒有之間沒有倍數(shù)關(guān)系，可以把較小的數(shù)依次除以2、3、4……直到求得的商是較大數(shù)的約數(shù)為止，這時的商就是兩個數(shù)的最大公約數(shù)．例如：求30和24的最大公約數(shù)．24÷4＝6，6是30的約數(shù)，所以30和24的最大公約數(shù)是6．

　　 八、求差判定法．

　　如果兩個數(shù)相差不大，可以用大數(shù)減去小數(shù)，所得的差與小數(shù)的最大公約數(shù)就是原來兩個數(shù)的最大公約數(shù)．例如：求78和60的最大公約數(shù)．78－60＝18，18和60的最大公約數(shù)是6，所以78和60的最大公約數(shù)是6．

　　
如果兩個數(shù)相差較大，可以用大數(shù)減去小數(shù)的若干倍，一直減到差比小數(shù)小為止，差和小數(shù)的最大公約數(shù)就是原來兩數(shù)的最大公約數(shù)．例如：求92和16的最大公約數(shù)．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公約數(shù)是4，所以92和16的最大公約數(shù)就是4．

　　九、輾轉(zhuǎn)相除法．

　　當兩個數(shù)都較大時，采用輾轉(zhuǎn)相除法比較方便．其方法是：

　　以小數(shù)除大數(shù)，如果能整除，那么小數(shù)就是所求的最大公約數(shù)．否則就用余數(shù)來除剛才的除數(shù)；再用這新除法的余數(shù)去除剛才的余數(shù)．依此類推，直到一個除法能夠整除，這時作為除數(shù)的數(shù)就是所求的最大公約數(shù)．

　　例如：求4453和5767的最大公約數(shù)時，可作如下除法．

　　5767÷4453＝1余1314

　　4453÷1314＝3余511

　　1314÷511＝2余292

　　511÷292＝1余219

　　292÷219＝1余73

　　219÷73＝3

　　于是得知，5767和4453的最大公約數(shù)是73．

　　輾轉(zhuǎn)相除法適用比較廣，比短除法要好得多，它能保證求出任意兩個數(shù)的最大公約數(shù)．

int?GetGCDRec(int?n,?int?m)
{
????if?(m?<?n)
????{
????????m?^=?n;
????????n?^=?m;
????????m?^=?n;
????}

????if?(n?==?0)
????????return?m;
????else
????????return?GetGCDRec(n,?m?%?n);
}

輾轉(zhuǎn)相除法，求一個數(shù)組中所有數(shù)的最大公約數(shù)

int?GetGCD(int?*arr,?int?len)
{
????int?iMax?=?arr[0],?iCurr,?iRemainder;

????for(int?i?=?1;?i?<?len;?i++)
????{
????????iCurr?=?arr[i];

????????if?(iMax?<?iCurr)
????????{
????????????iMax?^=?iCurr;
????????????iCurr?^=?iMax;
????????????iMax?^=?iCurr;
????????}

????????iRemainder?=?iMax?%?iCurr;

????????while?(iRemainder)
????????{
????????????iMax?=?iCurr;
????????????iCurr?=?iRemainder;
????????????iRemainder?=?iMax?%?iCurr;
????????}
????????
????????iMax?=?iCurr;
????}//for

????return?iMax;

}

最小公倍數(shù)就是乘積除以最大公約數(shù)

int?GetLCM(int?*arr,?int?len)
{
????int?multiple?=?1;

????for?(int?i?=?0;?i?<?len;?i++)
????????multiple?*=?arr[i];

????return?multiple?/?GetGCD(arr,?len);
}

?