LeetCode 263 Ugly Number：判斷醜數

題目描述

編寫程式判斷給定數是否為醜數。醜數定義：質因子僅包含 2, 3, 5 的正整數。例如 6, 8 是醜數，14 不是（含質因子 7）。規定 1 為醜數。

解題思路

若數為醜數，持續除以 2、3、5 直到無法整除，最終結果必為 1。反之若剩餘值 ≠ 1，則含有其他質因子。

Java 實現

public class Ugly_Number {
    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            System.err.println(i + " == " + isUgly(i));
        }
    }

    public static boolean isUgly(int num) {
        if (num == 1) return true;
        while (num >= 2 && num % 2 == 0) num /= 2;
        while (num >= 3 && num % 3 == 0) num /= 3;
        while (num >= 5 && num % 5 == 0) num /= 5;
        return num == 1;
    }
}

複雜度分析

• 時間複雜度：O(log n)，每次除以至少 2。
• 空間複雜度：O(1)。