0263. 丑数
题目地址(263. 丑数)
https://leetcode-cn.com/problems/ugly-number/
题目描述
编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 2, 3, 5 的正整数。示例 1:输入: 6输出: true解释: 6 = 2 × 3示例 2:输入: 8输出: true解释: 8 = 2 × 2 × 2示例 3:输入: 14输出: false解释: 14 不是丑数，因为它包含了另外一个质因数 7。说明：1 是丑数。输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。前置知识
数学
因数分解
公司
阿里
腾讯
百度
字节
思路
题目要求给定一个数字，判断是否为“丑陋数”(ugly number), 丑陋数是指只包含质因子 2, 3, 5 的正整数。
根据定义，我们将给定数字除以 2、3、5(顺序无所谓)，直到无法整除。 如果得到 1，说明是所有因子都是 2 或 3 或 5，如果不是 1，则不是丑陋数。
这就好像我们判断一个数字是否为 n(n 为大于 1 的正整数)的幂次方一样，我们只需要 不断除以 n，直到无法整除，如果得到 1，那么就是 n 的幂次方。 这道题的不同在于 它不再是某一个数字的幂次方，而是三个数字（2，3，5），不过解题思路还是一样的。
转化为代码可以是：
while (num % 2 === 0) num = num / 2;while (num % 3 === 0) num = num / 3;while (num % 5 === 0) num = num / 5;return num === 1;我下方给出的代码是用了递归实现，只是给大家看下不同的写法而已。
关键点
数论
因数分解
代码
语言支持：JS, C++, Java, Python
Javascript Code:
/* * @lc app=leetcode id=263 lang=javascript * * [263] Ugly Number *//** * @param {number} num * @return {boolean} */var isUgly = function (num) { // TAG: 数论 if (num <= 0) return false; if (num === 1) return true; const list = [2, 3, 5]; if (list.includes(num)) return true; for (let i of list) { if (num % i === 0) return isUgly(Math.floor(num / i)); } return false;};复杂度分析
时间复杂度：$O(logN)$
空间复杂度：$O(logN)$
C++ Code:
class Solution {public: bool isUgly(int num) { int ugly[] = {2,3,5}; for(int u : ugly) { while(num%u==0 && num%u < num) { num/=u; } } return num == 1; }};Java Code:
class Solution { public boolean isUgly(int num) { int [] ugly = {2,3,5}; for(int u : ugly) { while(num%u==0 && num%u < num) { num/=u; } } return num == 1; }}Python Code:
# 非递归写法class Solution: def isUgly(self, num: int) -> bool: if num <= 0: return False for i in (2, 3, 5): while num % i == 0: num /= i return num == 1复杂度分析
时间复杂度：$O(logN)$
空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最后更新于
这有帮助吗？