丑数 就是只包含质因数 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$ 和负整数一定不是丑数。
当 $n>0$ 时，若 $n$ 是丑数，则 $n$ 可以写成 $n = 2^a \times 3^b \times 5^c$ 的形式，其中 $a,b,c$ 都是非负整数。特别地，当 $a,b,c$ 都是 $0$ 时，$n=1$。
为判断 $n$ 是否满足上述形式，可以对 $n$ 反复除以 $2,3,5$，直到 $n$ 不再包含质因数 $2,3,5$。若剩下的数等于 $1$，则说明 $n$ 不包含其他质因数，是丑数；否则，说明 $n$ 包含其他质因数，不是丑数。
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
int[] factors = {2, 3, 5};
for (int factor : factors) {
while (n % factor == 0) {
n /= factor;
}
}
return n == 1;
}
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
| var isUgly = function(n) {
if (n <= 0) {
return false;
}
const factors = [2, 3, 5];
for (const factor of factors) {
while (n % factor === 0) {
n /= factor;
}
}
return n == 1;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
| var factors = []int{2, 3, 5}
func isUgly(n int) bool {
if n <= 0 {
return false
}
for _, f := range factors {
for n%f == 0 {
n /= f
}
}
return n == 1
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
factors = [2, 3, 5]
for factor in factors:
while n % factor == 0:
n //= factor
return n == 1
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool isUgly(int n) {
if (n <= 0) {
return false;
}
vector<int> factors = {2, 3, 5};
for (int factor : factors) {
while (n % factor == 0) {
n /= factor;
}
}
return n == 1;
}
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
| bool isUgly(int n) {
if (n <= 0) {
return false;
}
int factors[] = {2, 3, 5};
for (int i = 0; i < 3; i++) {
while (n % factors[i] == 0) {
n /= factors[i];
}
}
return n == 1;
}
|
复杂度分析
