面試題目記錄(2)

題目敘述

輸入兩個數字N1、N2 輸出N1、N2、兩數的最大公因數、兩數的最小公倍數

解題思考

求解最大公因數算是基本題，使用輾轉相除法找出答案，進一步再找出最小公倍數，為國中數學基礎。

實作

建立輾轉相除法的function gcd()，以遞迴方式呈現。最小公倍數以下方質因數分解後的例子作為說明:

N1 = 12, 即2*2*3 N2 = 30, 即2*3*5 因此最大公因數為共同的2*3 最小公倍數為最大公因數去乘上兩數分別多出來的部分，即N1中的2還有N2中的5 所以最大公因數為2*3 = 6，最小公倍數為(2*3)*2*5 = 60

感想

我認為最大的考點在於求最大公因數時輾轉相除法的實作，可以使用遞迴或是迴圈加上變數交換來寫。最小公倍數的部分倒是沒記得公式，只記得基本原理上的求法。

當然！結果上是相同的。