最大公因數 (Greatest Common Divisor)

http://4rdp.blogspot.com/2012/09/blog-post_22.html

最近小朋友剛學最大公因數 (Greatest Common Divisor)，問我兩數之間最大公因數求解，他說老師利用輾轉相減求之，其方法如下：

以較大數減較小數，較大數變小後，再繼續比較，直到兩數相等或其中某數值變成1

我畫了上圖解說，他很快理解原理。

例一：有兩數分別為 A = 7 和 B = 5，
A = 7 - 5 = 2, B = 5
A = 2, B = 5 - 2 = 3
A = 2, B = 3 - 2 = 1
最大公因數為 1

例二：有兩數分別為 A = 14 和 B = 10，
A = 14 - 10 = 4, B = 10
A = 4, B = 10 - 4 = 6
A = 4, B = 6 - 4 = 2
A = 4 - 2 = 2, B = 2
最大公因數為 2

有興趣的讀者可以延伸閱讀 NXT 無法使用遞歸 (Recursion) 一文，參考程式碼。