更相減損術的算法步驟

更相減損術，又稱"等值算法"，“關於約分問題，實質是如何求分子，分母最大公約數的問題。

例如：求441和378的最大公約數

1、由於均不爲偶數，不必同除以2（同爲偶數則需要）

2、把大數減去小數441-378=63

3、比較減數和差的大小，用大的減去小的378-63=315

4、同上315-63=252252-63=189189-63=126126-63=63

5、當差在運算過程中出現2次相同的時候，差即爲最大公約數（63出現了2次）。

其實這比較麻煩，當數較大時，可以用輾轉相除法做容易些

例如

將用更相減損術求147和63的最大公約數的過程用程序框圖寫出來

例1、用更相減損術求98與63的最大公約數。

解：由於63不是偶數，把98和63以大數減小數，並輾轉相減：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公約數等於7。

例2、用更相減損術求260和104的最大公約數。

解：由於260和104均爲偶數，首先用2約簡得到130和52，再用2約簡得到65和26。

此時65是奇數而26不是奇數，故把65和26輾轉相減：

65-26=39

39-26=13

26-13=13

所以，260與104的最大公約數等於13乘以第一步中約掉的兩個2，即13*2*2=52。