有兩個自然數a和b，如果a能被b整除，那麼，b就叫做a的約數。
兩個或多個自然數的共有約數中最大的一個，叫做它們的最大公約數，也稱最大公因數、最大公因數。
求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、輾轉相減法、更相減損法等。
【問題】
輸入兩個正整數x和y，求它們的最大公約數。
【編程解題】
下面我們使用輾轉相除法求出兩個數的最大公約數。
輾轉相除法
輾轉相除法的算法步驟：給定兩個正整數x、y（x>y），用x除以y等到餘數z。如果餘數z不為0就將y和z構成新的一組數（x=y，y=z），繼續上的除法操作，直到餘數z為0，這時y就是原來兩個正整數的最大公約數。
由於這個算法需要反覆執行除法運算，所以被形象地命名為“輾轉相除法”。
舉例說明，用輾轉相除法求255,75的最大公約數。
給定兩個數：255,75
第一次：用255除以75，餘數30；
第二次：用75除以30，餘數15；
第三次：用30除以15，餘數0；
這個時候我們得出255和75的最大公約數是15.
Scratch編程實現算法：
根據上面的算法步驟，我們編寫一個名為“輾轉相除法”的模塊，用來求兩個數的最大公約數。該模塊的完成代碼如下：
下面編寫調用“輾轉相除法”模塊的主程序，用來求255和75的最大公約數。主程序代碼如下：
點擊小綠旗運行程序，求得255和75的最大公約數是15。
分享到:
閱讀更多 酷叮貓少兒編程 的文章
