263. 丑数
题目描述
如果一个正整数分解质因数后，只含 2、3、5 这几种质因数，就称它为丑数。1 没有质因数，也算丑数。0 和负数都不是丑数。
输入一个整数 n。n 是丑数时返回 true，否则返回 false。
示例 1
输入：n = 6 输出：true
解释：6 = 2 × 3。
示例 2
输入：n = 1 输出：true
解释：1 没有任何质因数。
示例 3
输入：n = 14 输出：false
解释：14 = 2 × 7，多了质因数 7。
数据范围
-2^31 <= n <= 2^31 - 1
解题思路
非正数直接不是丑数。对正数，把因子 2、3、5 依次除干净：只要能整除就一直除。如果最后剩下 1，说明没有别的质因数；否则剩下的部分就含有其他质因数。
为什么正确
原 n = 2^a · 3^b · 5^c · 当前 n，当前 n 中没有已处理过的质因数。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
n <= 0 必须先判掉：0 能被任何数整除，不处理会死循环；负数也不是丑数。另外 1 是丑数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
for p in (2, 3, 5):
while n % p == 0:
n //= p
return n == 1class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
for (int p : new int[]{2, 3, 5}) {
while (n % p == 0) {
n /= p;
}
}
return n == 1;
}
}class Solution {
public:
bool isUgly(int n) {
if (n <= 0) {
return false;
}
for (int p : {2, 3, 5}) {
while (n % p == 0) {
n /= p;
}
}
return n == 1;
}
};func isUgly(n int) bool {
if n <= 0 {
return false
}
for _, p := range []int{2, 3, 5} {
for n%p == 0 {
n /= p
}
}
return n == 1
}var isUgly = function(n) {
if (n <= 0) {
return false;
}
for (const p of [2, 3, 5]) {
while (n % p === 0) {
n /= p;
}
}
return n === 1;
};function isUgly(n: number): boolean {
if (n <= 0) {
return false;
}
for (const p of [2, 3, 5]) {
while (n % p === 0) {
n /= p;
}
}
return n === 1;
}