題目描述

判斷給定數是否為醜數。醜數定義：質因數僅包含 2、3、5 的正整數。1 視為醜數。例如 6(2×3)、8(2³) 是醜數，14(2×7) 不是。

核心算法：連續除以 2、3、5

反覆除以 2、3、5 直到不能整除，若最終結果為 1 則為醜數，否則包含其他質因數。

代碼實現

// Runtime: 2 ms
public class Solution {
    public boolean isUgly(int num) {
        if (num == 0) return false; // 0 不是正整數
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
}

複雜度分析

• 時間：O(log n) —— 每次除法至少減半
• 空間：O(1)

邊界情況

• num ≤ 0：直接返回 false（題目定義正整數）
• num = 1：循環不執行，直接返回 true
• INT_MAX：除法安全，無溢出風險

擴展：Ugly Number II（第 n 個醜數）

見下一文檔，使用三指針動態生成有序醜數序列。