如何判断一个数是不是丑数？（LeetCode 263）

简化版

丑数是质因数只包含 2、3、5 的正整数。判断方法很直接：如果 n <= 0 返回 false；不断把 n 中的因子 2、3、5 除干净，最后如果剩下 1，就是丑数，否则说明还有其他质因数。

详细版

boolean isUgly(int n) {
    if (n <= 0) return false;
    int[] factors = {2, 3, 5};
    for (int f : factors) {
        while (n % f == 0) {
            n /= f;
        }
    }
    return n == 1;
}

例如 6 = 2 * 3 是丑数，14 = 2 * 7 不是，因为剩下了因子 7。注意 1 通常被定义为丑数，因为它没有其他质因数。

完整版教学

一、丑数定义要先说清

丑数不是“长得丑的数”，而是质因数集合被限制在 {2,3,5} 内的正整数。

1 是丑数
6 = 2 * 3 是丑数
8 = 2 * 2 * 2 是丑数
14 = 2 * 7 不是丑数

判断时不要去枚举所有质因数，只需要把允许的质因数除掉。

二、为什么除到最后看 1

任意正整数都可以分解成质因数乘积。如果把所有 2、3、5 都除干净：

原数	除掉 2/3/5 后剩余	结论
6	1	是丑数
8	1	是丑数
14	7	不是丑数
1	1	是丑数

剩余为 1，说明没有其他质因数；剩余大于 1，说明还藏着不允许的质因数。

记忆钩子：丑数判断不是找所有因子，而是“把允许的因子洗掉，看最后有没有残渣”。

三、为什么 n <= 0 直接 false

题目定义的是正整数。0 可以被 2、3、5 无限整除的直觉容易误导，但它没有正常的质因数分解；负数也不属于定义范围。

if (n <= 0) return false;

这句必须放在除法循环前面，否则 0 % 2 == 0 会导致死循环。

四、循环除法如何写

对每个允许因子，用 while 而不是 if，因为一个因子可能出现多次。

n = 8
除 2: 8 -> 4 -> 2 -> 1

如果只除一次，8 会变成 4，最后误判为不是丑数。

五、复杂度怎么分析

每次除法都会让 n 至少缩小一半、三分之一或五分之一。循环次数大约是质因数指数之和，最坏 O(log n)。

空间只用几个变量，是 O(1)。

六、和第 n 个丑数的区别

判断一个数是不是丑数是除因子；求第 n 个丑数则是动态规划/三指针生成序列。

判断题：给 n，问 yes/no
生成题：给 index，求第 index 个丑数

面试时要先识别题型，不要把简单判断题写成复杂生成题。

七、常见误区与追问

• 误区：把 1 判成 false。 按常见题目定义，1 是丑数。
• 误区：对 0 进入 while 除法。 0 % 2 == 0 会造成死循环。
• 误区：每个因子只除一次。 因子可能重复出现，必须用 while。
• 追问：为什么剩余为 1 就是丑数？ 说明所有质因数都来自 2、3、5。
• 追问：复杂度是多少？ 除法次数和因数指数相关，通常写 O(log n)。
• 追问：第 n 个丑数怎么做？ 用三个指针分别生成乘 2、乘 3、乘 5 的候选。

八、加强记忆

丑数判断的模板是：正数校验、除 2、除 3、除 5、看是否为 1。尤其记住 n <= 0 要先返回，否则 0 会把循环拖进坑里。它是一道“定义转代码”的题，别把它复杂化。