一【题目类别】

• 数学

二【题目难度】

• 简单

三【题目编号】

• 263.丑数

四【题目描述】

• 丑数 就是只包含质因数 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 。

六【解题思路】

• 根据题目的定义，丑数只包含2、3和5质因数，形式为：$n=2^a\times 3^b\times 5^c$，所以我们只需要不停的除以2、3和5，如果最后的结果为1，说明此数字的质因数没有其他数字，就是丑数，否则就不是丑数
• 还要注意负数和0不是丑数，要特判一下
• 最后返回结果即可

七【题目提示】

• $-2^{31}<=n<=2^{31}-1$

八【时间频度】

• 时间复杂度：$O(logn)$，其中$n$为传入参数的大小
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

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;}
}

2. C语言版

bool 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;
}

3. Python版

class Solution:def isUgly(self, n: int) -> bool:if n <= 0:return Falsewhile n % 2 == 0:n //= 2while n % 3 == 0:n //= 3while n % 5 == 0:n //= 5return n == 1

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版