0263. Ugly Number ================= 题目信息 -------- :题号: 0263 :难度: Easy :主题: 数学、质因数、整除 :原题: `LeetCode 0263 `_ :重点: 只允许质因数 2、3、5、输入必须为正数、``1`` 没有质因数但仍视为丑数 题目重述 -------- 给定一个 32 位有符号整数 ``n``,判断它是否为丑数。丑数必须是正整数,并且它的全部质因数只能来自 ``2``、``3`` 和 ``5``;只要还含有其他质因数,就不是丑数。 ``n`` 位于 ``[-2^31, 2^31 - 1]``。``1`` 没有质因数,按照题目定义仍属于丑数;``0`` 和所有负数都不属于丑数。函数只返回布尔结果,不需要给出质因数分解。 自建示例 -------- 只含允许的质因数: .. code-block:: text 输入:n = 45 输出:true 解释:45 = 3 × 3 × 5,所有质因数都属于 2、3、5。 混入其他质因数: .. code-block:: text 输入:n = 14 输出:false 解释:14 = 2 × 7,其中质因数 7 不在允许集合中。 定义边界: .. code-block:: text 输入:n = 1 输出:true 解释:题目明确把 1 视为丑数,尽管它没有质因数。 依次消除允许的质因数 -------------------- 若 ``n`` 是丑数,它可以写成 ``2^a 3^b 5^c``。不断地在能整除时除以 2、3、5, 会消掉所有允许的质因数;若最后恰好剩下 1,说明没有别的质因数。若剩下大于 1 的数, 它包含某个不属于集合 ``{2,3,5}`` 的质因数,因而不是丑数。 输入必须先为正数;``1`` 不会进入除法循环但应直接判为真。 正确性说明 ---------- 每次整除只移除一个允许质因数的幂,不会改变是否含有其他质因数。循环结束时, 2、3、5 的全部因子已经被移除;剩余值为 1 当且仅当原数没有其他质因数。非正数不符合丑数定义, 所以先返回假完整覆盖边界。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool isUgly(int n) { if (n <= 0) return false; for (int factor : {2, 3, 5}) { while (n % factor == 0) n /= factor; } return n == 1; } }; 代码分析 -------- 每次成功除法都会至少减少一个质因数幂,循环次数为 ``O(log n)``,额外空间为 ``O(1)``。 所有运算都在正数范围内进行,不会触发负数取模或 ``INT_MIN`` 的绝对值问题。