LeetCode Ugly Number：判斷醜數 — 僅含質因子 2、3、5

題目描述

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

範例： 6=2×3 → true；14=2×7 → false。

解題思路

不斷除以 2、3、5，直到無法整除。若最終結果為 1，則為醜數。

參考代碼 (C++)

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

複雜度分析

• 時間：O(log n) —— 每次除以至少 2。
• 空間：O(1)。