求最大公約數的兩種算法案例

李彥峰

求最大公約數有兩種經典算法，即輾轉相除法與更相減損術。

一、輾轉相除法

輾轉相除法最早出現(xiàn)于公元300年的古-希臘作家歐幾里得的《幾何原本》中，也被稱為歐幾里得算法，其主要作用是求兩個正整數的最大公約數。

輾轉相除法的算理：對于給定的整數。和6，若a≥b，則a=qb+r，此時（a，b）=（b，r）。我們把整數a，b的最大公約數用記號（a，b）來表示，即a和b的最大公約數與b和r（r為a除以b的余數）的最大公約數是相等的。

用輾轉相除法求兩個正整數m，n（m>n）的最大公約數的步驟：

第1步，給定兩個正整數m，n。

第2步，計算m除以n所得余數r。

第3步，m=n，n=r。

第4步，若r=0，則m，n的最大公約數等于m；否則返回第2步。

輾轉相除法求最大公約數的程序框圖如圖1所示。

二、更相減損術

更相減損術是《九章算術》里的一種求兩個正整數最大公約數的算法。

更相減損術求最大公約數的步驟：

第1步，任意給定兩個正整數，判斷它們是否都是偶數，若是偶數，用2約簡；若不是偶數，執(zhí)行第2步。

第2步，以較大的數減去較小的數，接著把所得的差與較小的數比較，并以大數減小數。繼續(xù)這個操作，直到所得的數相等為止，則這個數（等數）或這個數與約簡的數的乘積就是所求的最大公約數。

更相減損術求最大公約數的程序框圖如圖2所示，其中m，n為正整數，且m，n都不是偶數。

如果m，n均為偶數，則先用2約簡，直到不能同時用2約簡為止，然后把約簡所得的結果以較大的數減去較小的數進行輾轉相減，得到“等數”。“等數”與約簡的數的乘積就是所求的最大公約數。

（責任編輯 郭正華）