编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 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]。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ugly-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目要求给定一个数字,判断是否为“丑陋数”(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;
我下方给出的代码是用了递归实现,只是给大家看下不同的写法而已。
/*
* @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;
};