LeetCode 263 醜數判斷：遞歸除以 2/3/5 因子

題目描述

判斷給定正整數是否為醜數。醜數定義：質因子只包含 2、3、5。約定 1 為醜數，0 不是。

範例：

6  = 2 × 3 → true
8  = 2³    → true
14 = 2 × 7 → false (含因子 7)
1  → true

解題思路：遞歸除盡因子

不斷嘗試除以 2、3、5：

• 能整除 → 遞歸判斷商
• 均不能整除 → 若當前值為 1 則 true，否則 false

終止條件：num == 1（true）、num == 0（false，防死循環）。

時間複雜度：O(log n)，空間複雜度：O(log n)（遞歸棧，可改迭代 O(1)）。

C++ 參考實現

class Solution {
public:
    bool isUgly(int num) {
        if (num == 0) return false;
        if (num == 1) return true;
        if (num % 2 == 0) return isUgly(num / 2);
        if (num % 3 == 0) return isUgly(num / 3);
        if (num % 5 == 0) return isUgly(num / 5);
        return false;
    }
};

迭代版（O(1) 空間）

    bool isUglyIterative(int num) {
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }

核心要點總結

• 因子窮盡：只要能被 2/3/5 整除就除盡，剩下的若為 1 則合格
• 0 特判：0 無限可除，必須先排除
• 1 為基準：題目約定 1 是醜數，也是遞歸/迭代的成功終止條件
• 遞歸 vs 迭代：遞歸代碼極簡，迭代空間優化，面試建議給出兩版

醜數判斷是「因子分解」最簡應用，掌握「除盡指定質因子，看剩餘是否為 1」通用模式，可擴展至「超級醜數」（LeetCode 313）等變體。