0263. Ugly Number¶
题目信息¶
- 题号:
0263
- 难度:
Easy
- 主题:
数学、质因数、整除
- 原题:
- 重点:
只允许质因数 2、3、5、输入必须为正数、
1没有质因数但仍视为丑数
题目重述¶
给定一个 32 位有符号整数 n,判断它是否为丑数。丑数必须是正整数,并且它的全部质因数只能来自 2、3 和 5;只要还含有其他质因数,就不是丑数。
n 位于 [-2^31, 2^31 - 1]。1 没有质因数,按照题目定义仍属于丑数;0 和所有负数都不属于丑数。函数只返回布尔结果,不需要给出质因数分解。
自建示例¶
只含允许的质因数:
输入:n = 45
输出:true
解释:45 = 3 × 3 × 5,所有质因数都属于 2、3、5。
混入其他质因数:
输入:n = 14
输出:false
解释:14 = 2 × 7,其中质因数 7 不在允许集合中。
定义边界:
输入: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++ 实现¶
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 的绝对值问题。