LeetCode 263. 醜數判斷：質因子分解法 C 語言 O(log n) 解法

LeetCode 263. 醜數判斷：質因子分解法 C 語言 O(log n) 解法

判斷正整數是否為醜數：質因子僅包含 2、3、5。1 視為醜數。本文提供**連續除以 2、3、5 直到不可除**，檢查餘數是否為 1 的極簡解法，時間 O(log n)，空間 O(1)。

核心邏輯：質因子剝離

若 n 只含質因子 2,3,5，反覆除以 2、3、5 後必剩 1。否則剩下其他質因子（如 7、11），不等於 1。

C 語言實現

bool isUgly(int num) {
    if (num <= 0) return false; // 非正數非醜數
    if (num == 1) return true;  // 1 是醜數

    // 連續除以 2
    while (num % 2 == 0) num /= 2;
    // 連續除以 3
    while (num % 3 == 0) num /= 3;
    // 連續除以 5
    while (num % 5 == 0) num /= 5;

    return num == 1; // 剩 1 說明只含 2,3,5
}

關鍵點解析

• 順序無關**：先除 2 再除 3 再除 5，或任何順序，結果相同。
• 邊界處理**：`num <= 0` 直接 false（負數、0 無質因子分解）；`num == 1` 直接 true（空乘積約定為 1）。
• 循環條件 `num % p == 0`**：而非 `num >= p`，避免 `num=1` 時誤入循環（1%2=1 不進入，安全）。
• 時間復雜度**：每次除法至少將數值縮減因子 p≥2，循環次數 ≤ log₂ n + log₃ n + log₅ n = O(log n)。

測試用例

擴展：第 n 個醜數 (LeetCode 264 / 剑指 Offer 49)

動態規劃三指針法：維護三個指針 `p2, p3, p5` 指向下一個乘 2/3/5 產生新醜數的位置，每次取最小值並移動對應指針。O(n) 時間 O(n) 空間。

總結

醜數判斷是「質因子分解」思想的直接應用：**不斷剝離允許的質因子，看剩餘是否為 1** 代碼極簡、邏輯鐵clad、無邊界陷阱。面試必會、刷題秒殺、工程可直接用作「質因數過濾」預處理步驟。