題目描述:
判斷一個整數 n 是否為醜數(Ugly Number)。醜數定義為只包含質因數 2、3、5 的正整數。1 被視為醜數。
解題思路:
不斷將 n 除以 2、3、5,直到無法整除為止。若最終結果為 1,代表 n 的所有質因數都在 {2, 3, 5} 中,即為醜數。
n <= 0,直接回傳 false(醜數必須是正整數)。n 能被 2 整除時,持續除以 2。n 能被 3 整除時,持續除以 3。n 能被 5 整除時,持續除以 5。n 是否等於 1。時間複雜度:O(log n) — 每次除以 2、3 或 5 都使 n 至少減半,最多除 log₂(n) 次。
空間複雜度:O(1) — 只使用常數額外空間。
1. If n <= 0, return false 2. While n is divisible by 2: n = n / 2 3. While n is divisible by 3: n = n / 3 4. While n is divisible by 5: n = n / 5 5. Return n == 1
遞迴法:基礎情況為 n == 1 回傳 true,n <= 0 回傳 false。若 n 可被 2/3/5 整除則遞迴呼叫 isUgly(n/factor)。邏輯等價但有遞迴開銷,不如迭代法直接。
統一迴圈法:用一個 for 迴圈遍歷 [2, 3, 5],對每個因子持續除。程式碼更簡潔且易於擴展(若質因數集合改變):for (int p : {2, 3, 5}) while (n % p == 0) n /= p;。