0263. Ugly Number

题目信息

题号:

0263

难度:

Easy

主题:

数学、质因数、整除

原题:

LeetCode 0263

重点:

只允许质因数 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 的绝对值问题。