# h1TQC+ python 考試 最小公倍數 不可使用math模組

上週考試結果遇到最小公倍數的題目BUT 考古題目沒有 CODEJUGER也沒有
GOTOP教材也沒有

直接寫不出來
怒寫一波筆記!!!!!

在 TQC+ Python 考試中，如果您需要計算兩個數字的最小公倍數（LCM），而不允許使用 `math` 模組，您可以根據以下步驟來實現：

### 最小公倍數 least common multiple 的計算
最小公倍數可以透過最大公因數（GCD）來計算，公式如下：

{最小公倍數}(a, b) 為

|a * b| / {最大公因數} (a, b)

### 最大公因數的計算 Greatest Common Divisor
您可以使用輾轉相除法來計算 GCD。以下是計算 GCD 的方法：

def gcd(a, b):
    while b: #這個條件代表只要 b 的值不為 0，就繼續進行迴圈
        a, b = b, a % b
    return a

### 實作最小公倍數 least common multiple
接下來，根據上述公式來計算最小公倍數：

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# 主程式
num1 = int(input("請輸入第一個數字: "))
num2 = int(input("請輸入第二個數字: "))

result = lcm(num1, num2)
print(f"{num1} 和 {num2} 的最小公倍數是: {result}")

### 完整範例程式碼
以下是完整的程式碼，讓您可以直接使用：

def gcd(a, b):
    while b:
        a, b = b, (a % b) #a除以b的餘數
    return a

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# 主程式
num1 = int(input("請輸入第一個數字: "))
num2 = int(input("請輸入第二個數字: "))

result = lcm(num1, num2)
print(f"{num1} 和 {num2} 的最小公倍數是: {result}")

### 說明
1. **`gcd(a, b)` 函數**：計算兩個數字的最大公因數，使用輾轉相除法。
2. **`lcm(a, b)` 函數**：使用 GCD 計算最小公倍數。
3. **主程式**：從使用者輸入兩個數字，然後計算並輸出它們的最小公倍數。

這段程式碼可以在不使用 `math` 模組的情況下計算最小公倍數。

# 另一種在維基百科上的更簡約的寫法:

在這段 Python 代碼中，`lambda` 是用來創建匿名函數的一種方式。

### 解釋代碼：

#### Lambda 寫法：

GCD = lambda a, b: (GCD(b, a % b) if a % b else b)

這行代碼使用了 Python 中的 lambda 表達式來實現「最大公因數」（GCD, Greatest Common Divisor）的計算，它使用了遞迴的方式來計算兩個整數的最大公因數。讓我們逐步來解釋這行代碼的運作方式。

### 1. `lambda` 表達式的基本概念
`lambda` 是一種簡潔的匿名函數表達方式，通常用於定義一些簡短的函數。格式如下：

lambda 參數: 表達式

在這段代碼中：

GCD = lambda a, b: (GCD(b, a % b) if a % b else b)

- `GCD` 是定義的函數名稱。
- `a` 和 `b` 是函數的兩個參數。
- `GCD(b, a % b) if a % b else b` 是這個 lambda 表達式的核心邏輯，通過遞迴來計算最大公因數。

### 2. 邏輯分析
`GCD(b, a % b) if a % b else b` 是使用條件運算符來實現的，邏輯如下：

- **條件部分：** `if a % b`，這部分代表如果 `a % b` 不等於 `0`，即 `a` 不能被 `b` 整除。
- 如果 `a % b` 不為 `0`，則表示還需要繼續進行 GCD 的計算，這時遞迴調用 `GCD(b, a % b)`。
- 如果 `a % b` 等於 `0`，則表示 `b` 是 `a` 和 `b` 的最大公因數，因為此時 `a` 能夠被 `b` 整除。

### 3. 例子：GCD(48, 18)
假設你要計算 `GCD(48, 18)`：

1. 初次調用：
- `a = 48`，`b = 18`
- `a % b = 48 % 18 = 12`，因為 `a % b` 不等於 `0`，所以繼續計算：`GCD(18, 12)`

2. 第二次調用：
- `a = 18`，`b = 12`
- `a % b = 18 % 12 = 6`，因為 `a % b` 不等於 `0`，所以繼續計算：`GCD(12, 6)`

3. 第三次調用：
- `a = 12`，`b = 6`
- `a % b = 12 % 6 = 0`，因為 `a % b` 等於 `0`，返回 `b`，即 `6`

最終結果是 `6`，這就是 `48` 和 `18` 的最大公因數。

### 4. 遞迴的核心邏輯
這段代碼實際上是一個遞迴函數，每次遞迴中，通過交換參數並計算餘數，問題的規模會不斷縮小，直到餘數為 `0`。此時，遞迴停止並返回最大公因數。

這是基於 **歐幾里得算法** 的特點，這個算法的核心思想是：
- 如果 `a` 能夠被 `b` 整除，那麼最大公因數就是 `b`。
- 否則，最大公因數等於 `b` 和 `a % b` 的最大公因數。

### 5. 小心遞迴深度問題
雖然這樣的寫法非常簡潔，但需要注意，如果 `a` 和 `b` 都是非常大的數字，或者它們之間的差距非常大，可能會導致遞迴深度過大而導致 **遞迴深度超過限制** 的錯誤。Python 對遞迴深度是有預設的限制的，一般可以通過調整來增加最大遞迴深度，但在計算特別大的數時，這樣的遞迴方式效率可能不如迴圈。

### 6. 使用的替代方案
如果你想避免遞迴深度的問題，可以考慮使用前面迴圈版本的實現，如：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

這樣的迴圈版本可以避免因為過多的遞迴層次而導致的錯誤。

### 總結
- `lambda a, b: (GCD(b, a % b) if a % b else b)` 是一個使用遞迴的匿名函數來計算最大公因數。
- 當 `a % b != 0` 時，函數繼續遞迴呼叫 `GCD(b, a % b)`；當 `a % b == 0` 時，返回 `b` 作為結果。
- 這種方式使用了 **歐幾里得算法**，該算法非常高效，但是需要注意遞迴深度的限制問題。

這樣寫簡潔且容易理解，但在需要處理大量數據或大數時，最好考慮非遞迴的迴圈版本，以避免深度遞迴的風險。

這段代碼是用來計算兩個整數的最大公因數 (GCD, Greatest Common Divisor)。它使用的是「歐幾里得算法」（Euclidean Algorithm）進行遞迴求解，直到餘數為 0。

#### 使用 `def` 寫法：

def GCD(a, b):
    if a % b: #這裡在講如果a mod b 不為零 為True 
        return GCD(b, a % b)
    else:
        return b

這段代碼與上面 `lambda` 的方式功能相同，但使用了標準函數定義的方法。

### 補充概念:
`if a % b:` 是一種簡化的寫法，這裡的 `if a % b:` 實際上是在檢查 `a` 除以 `b` 的餘數是否不為零。這是 Python 中一種常見的布林運算寫法。

### 詳細解釋：

1. **`a % b`**：這是取餘數運算符，會返回 `a` 除以 `b` 的餘數。

2. **`if a % b:`**：在 Python 中，任何非零的數值被視為 `True`，而零則被視為 `False`。因此，這個條件語句會在 `a` 除以 `b` 的餘數不為零的時候返回 `True`，也就是說 `a` 不是 `b` 的倍數。

3. **相當於 `if a % b != 0:`**：這樣的寫法更明確地表達了這個邏輯。當 `a` 除以 `b` 產生的餘數不為零時，表示 `a` 不能被 `b` 整除，這樣的情況下會執行 `if` 語句中的代碼。

### 總結：
因此，`if a % b:` 和 `if a % b != 0:` 實際上是等價的，只是第一種寫法更為簡潔。這樣的寫法在 Python 中是很常見的，可以提高代碼的可讀性，特別是在進行條件判斷時。

# 另一種計算最小公倍數的方法:

inputst = input("input numbers split whith command :") #['2,3,4']
nums = inputst.split(",") #['2','3','4'] 字串轉為陣列LIST
nums = [int(x) for x in nums ] #[2,3,4] 字串陣列轉為數字陣列
nums.sort(reverse = True)#[4,3,2] 排列大到小 並反轉

lcm = nums[0]  #gcd=4
a = None  # 在迴圈外定義 a 變數，使其在 Variable Explorer 可見
while True:
    isLcm = True
    for i in nums:
        a = lcm % i  # 計算餘數，並將值賦給全域變數 a
        if a !=0:
            isLcm = False
            break
    if isLcm:
        break
    else:
        lcm += nums[0] # 因不是最小公倍數所以預設最大數 再來 加一次列表的最大數字
print(lcm)