找最大公因數和最小公倍數
找最大公因數(GCD)和最低公倍數(LCM)可以通過多種方法,如輾轉相除法或質因數分解。這裡,我將為你提供一個基於輾轉相除法的基本算法以及如何使用它來找出最大公因數和最低公倍數。
假設我們有兩個整數a和b。
最大公因數(GCD)可以通過輾轉相除法求得:
- 計算a和b的餘數(記為r)
- 如果r=0,那麼a就是最大公因數。
- 否則,將a和b更新為b和r,並重複步驟1和2。
最低公倍數(LCM)可以通過以下步驟求得:
- 將a和b的最大公因數(假設為m)從a和b中減去。
- 將新的a和b相乘,得到的結果就是最低公倍數。
下面是一個Python代碼示例,演示如何使用輾轉相除法來找出兩個數的最大公因數,並使用這個最大公因數來求出最低公倍數:
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
# 測試上述函式
print("最大公因數:", gcd(48, 36)) # 輸出結果應該是 12
print("最低公倍數:", lcm(48, 36)) # 輸出結果應該是 144
這段代碼中的gcd
函式實現了輾轉相除法,而lcm
函式使用gcd
函式的結果來計算最低公倍數。我們用一些示例來測試這兩個函式,結果應該符合預期。