解題說明
Ugly Number
題目描述：
判斷一個整數 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。
C++ 解法
複雜度分析
時間複雜度：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;。
延伸思考
- 如何找第 n 個醜數？（LeetCode 264 Ugly Number II）需要什麼不同的策略？
- 若質因數集合改為 {2, 3, 7}（Super Ugly Number 的特例），此算法需要怎樣修改？
- 1 為什麼被定義為醜數？從數學上如何解釋空集合的乘積等於 1？