求最大公約數(shù)的兩種算法案例

李彥峰

求最大公約數(shù)有兩種經(jīng)典算法，即輾轉(zhuǎn)相除法與更相減損術(shù)。

一、輾轉(zhuǎn)相除法

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

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

用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m，n（m>n）的最大公約數(shù)的步驟：

第1步，給定兩個(gè)正整數(shù)m，n。

第2步，計(jì)算m除以n所得余數(shù)r。

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

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

輾轉(zhuǎn)相除法求最大公約數(shù)的程序框圖如圖1所示。

二、更相減損術(shù)

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

更相減損術(shù)求最大公約數(shù)的步驟：

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

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

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

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

（責(zé)任編輯 郭正華）