题目

丑数 就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n，请你判断 n 是否为 丑数。如果是，返回 true；否则，返回 false。

示例 1：

• 输入：n = 6
• 输出：true
• 解释：6 = 2 × 3

示例 2：

• 输入：n = 1
• 输出：true
• 解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3：

• 输入：n = 14
• 输出：false
• 解释：14 不是丑数，因为它包含了另外一个质因数 7。

方法一：数学

思路及解法

根据丑数的定义，0 和负整数一定不是丑数。

当 时，若 是丑数，则 可以写成 的形式，其中 ,, 都是非负整数。特别地，当 ,, 都是 时，。

为判断 是否满足上述形式，可以对 反复除以 ,,，直到 不再包含质因数 ,,。若剩下的数等于 ，则说明 不包含其他质因数，是丑数；否则，说明 包含其他质因数，不是丑数。

代码

class Solution {
    func isUgly(_ n: Int) -> Bool {
        var n: Int = n
        if n <= 0 {
            return false
        }
        let factors: [Int] = [2, 3, 5]
        for factor in factors {
            while n % factor == 0 {
                n /= factor
            }
        }
        return n == 1
    }
}

复杂度分析

• 时间复杂度：。时间复杂度取决于对 除以 ,, 的次数，由于每次至少将 除以 ，因此除法运算的次数不会超过 。

• 空间复杂度：。

方法二：数学（二）

思路及解法

判断当前 是否可以整除 ，如果可以将 ；再判断是否可以整除 ，如果可以将 ；判断是否可以整除 ，可以的话将 ；
如果符合丑数只包含 或 或 的定义则最终的 值一定等于 。

代码

class Solution {
    func isUgly(_ n: Int) -> Bool {
        var n: Int = n
        while n >= 1 {
            if n % 2 == 0 {
                n /= 2
            } else if n % 3 == 0 {
                n /= 3
            } else if n % 5 == 0 {
                n /= 5
            } else {
                break
            }
        }
        return n == 1
    }
}

复杂度分析

• 时间复杂度：。

• 空间复杂度：。