在人教版小學五年級數學課本里，講到了最大公因數的概念：
為了幫助兒子更容易理解這個概念，我打算用編程的方法來講解。首先，我用一道題目引入：
假如你有一根長12米的鐵絲和一根長9米的鐵絲，要把它們截成同樣長的小段，要求沒有剩餘，請問，每段最長是幾米？
其實，我出的這道題是數學上的經典問題之一，其本質就是求兩數的最大公因數。
學習數學題，抽象思維很重要。因此，求最大公因數的問題可以轉換為以下描述：
假設有兩個自然數A和B，且A > B，它們的最大公因數是K。已知A, B，求K。
歷史上的數學家們對於這個問題曾經想出了很多不同的解法。早在距今 2300 多年前的古希臘，數學家歐幾里得在所著的《幾何原本》一書中就提出了一種方法：輾轉相除法，也叫歐幾里得算法。
歐幾里德《幾何原本》
輾轉相除法的思路是這樣的：
第一步，先用大數除以小數，即A÷B，看是否能整除。如果是，那麼B就是兩數的最大公因數，否則求餘數，記為C。
第二步：把B賦值給A, C賦值給B。繼續上一步的步驟，即A÷B，如果能整除，那麼此時的B就是兩數的最大公因數。否則，繼續以上步驟，直到能整除時，此時的除數B就是兩數的最大公約數。
用一句話概括如下：
不斷求兩數相除的餘數，用除數代替被除數，餘數代替除數，直到餘數為0，此時的除數就是最大公約數。
聽起來很簡單對不對？下面我們就來驗證一下：
先來看看上面那道題目 ，其實就是求12和9的最大公因數。
- 12÷9=1......3
- 9÷3=3.....0
上面那道題裡的12和9都比較小，因此只需要進行兩次計算就得出了答案：12和9的最大公因數是3。
那麼，如果是兩個較大的數呢？
求767和4453的最大公因數。其實多大的數都沒關係，方法還是一樣：
- 5767÷4453=1......1314
- 4453÷1314=3......511
- 1314÷511=2......292
- 511÷292=1......219
- 292÷219=1......73
- 219÷73=3......0
經過了6次計算，得到一個整除的算式：219÷73=3，此時的除數73就是兩數的最大公因數。
在信息學奧賽（National Olympiad in Informatics, 簡稱NOI）中，也會涉及到輾轉相除法。
在以上的計算中，我們已經知道了輾轉相除法的原理，接下來我們用程序來實現。
先畫個程序流程圖
然後在scratch實現：
藉助編程的方法學習數學，可以讓孩子很直觀地驗證自己的思路，也能增加趣味性，提升孩子學習數學 的興趣。讓孩子試著輸入任意數字，驗證一下答案吧：
閱讀更多 趣學聯盟 的文章
