英文原文
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return true if n is an ugly number.
Example 1:
Input: n = 6 Output: true Explanation: 6 = 2 × 3
Example 2:
Input: n = 8 Output: true Explanation: 8 = 2 × 2 × 2
Example 3:
Input: n = 14 Output: false Explanation: 14 is not ugly since it includes the prime factor 7.
Example 4:
Input: n = 1 Output: true Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Constraints:
-231 <= n <= 231 - 1
中文题目
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3
示例 2：
输入：n = 8 输出：true 解释：8 = 2 × 2 × 2
示例 3：
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
示例 4：
输入：n = 1 输出：true 解释：1 通常被视为丑数。
提示：
-231 <= n <= 231 - 1
通过代码
高赞题解
朴素解法
输入范围是 $-2^{31} <= n <= 2^{31} - 1$，我们只需要对输入进行分情况讨论即可：
- 如果 $n$ 不是正整数（即小于等于 0）：必然不是丑数，直接返回 false。
- 如果 $n$ 是正整数：我们对 $n$ 执行 2 3 5 的整除操作即可，直到 $n$ 被除干净，如果 $n$ 最终为 1 说明是丑数，否则不是丑数。
注意，2 3 5 先除哪一个都是可以的，因为乘法本身具有交换律。
代码：
class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
return n == 1;
}
}- 时间复杂度：当 $n$ 是以 2 为底的对数时，需要除以 $log{n}$ 次。复杂度为 $O(log{n})$
- 空间复杂度：$O(1)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~
也欢迎你 关注我 ，提供追求「证明」&「思路」的高质量题解
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 111084 | 215966 | 51.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 快乐数 | 简单 |
| 计数质数 | 中等 |
| 丑数 II | 中等 |
