【正文】 相減損術(shù)求最大公約數(shù)？ 討論結(jié)果： （ 1）短除法 求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來 . （ 2）窮舉法（也叫枚舉法） 窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便 是最大公約數(shù) . （ 3）輾轉(zhuǎn)相除法 輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法步驟可以描述如下： 第一步，給定兩個正整數(shù) m， n. 第二步，求余數(shù) r：計算 m 除以 n，將所得余數(shù)存放到變量 r 中 . 第三步，更新被除數(shù)和余數(shù)： m=n， n=r. 第四步，判斷余數(shù) r是否為 0，則輸出結(jié)果；否則轉(zhuǎn)向第二步繼續(xù)循環(huán)執(zhí)行 . 如此循環(huán)，直到得到結(jié)果為止 . 這種算法是由歐幾里得在公元前 300年左右首先提出的，因而又叫歐幾里得算法 . （ 4）更相減損術(shù) 我國早期也有解決求最大 公約數(shù)問題的算法，就是更相減損術(shù) . 《九章算術(shù)》是中國古 代的數(shù)學(xué)專著，其中的 “更相減損術(shù) ”也可以用來求兩個數(shù)的最大公約數(shù)，即 “可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也 .以等數(shù)約之 .”翻譯為現(xiàn)代語言如下： 第一步，任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù)，若是，用 2 約簡；若不是，執(zhí)行第二步 . 第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù) . （三） 應(yīng)用示例 例 1 用輾轉(zhuǎn)相除法求 8 251 與 6 105 的最大公約數(shù) ,寫出算法分析，畫出程序框圖，寫出算法程序 . 解： 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)： 8 251=6 1051+2 146. 由此可得， 6 105 與 2 146 的公約數(shù)也是 8 251 與 6 105的公約數(shù)，反過來， 8 251 與 6 105的公約數(shù)也是 6 105 與 2 146 的公約數(shù)，所以它們的最大公約數(shù)相等 . 對 6 105 與 2 146 重復(fù)上述步驟： 6 105=2 1462+1 813. 同理， 2 146 與 1 813 的最大公約數(shù)也 是 6 105 與 2 146 的最大公約數(shù) .繼續(xù)重復(fù)上述步驟： 2 146=1 8131+333， 1 813=3335+148， 333=1482+37， 148=374. 最后的除數(shù) 37 是 148 和 37 的最大公約數(shù)，也就是 8 251 與 6 105 的最大公約數(shù) . 這就是輾轉(zhuǎn)相除法 .由除法的性質(zhì)可以知道，對于任意兩個正整數(shù)，上述除