LeetCode_因式分解_简单_263.丑数

悠悠 2023-10-06 23:25 8阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**提示：**  
\-231 <= n <= 231 \- 1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/ugly-number

## 2.思路 ##

（1）因式分解  
如果 n 是丑数，那么一定存在非负整数 a、b、c，使得 n == 2a x 3b x 5c，并且当 a = b = c = 0 时，n = 1。所以为判断 n 是否满足上述形式，可以对 n 反复除以 2、3、5，直到 n 不再包含质因数 2、3、5 为止。如果剩下的数等于 1，则说明 n 不包含其他质因数，是丑数，返回 true；否则，说明 n 包含其他质因数，不是丑数，返回 false。

相关题目：  
[LeetCode\_动态规划\_中等\_264.丑数 II][LeetCode_264._ II]  
[LeetCode\_动态规划\_中等\_313.超级丑数][LeetCode_313.]  
[LeetCode\_容斥原理\_二分搜索\_困难\_878.第 N 个神奇数字][LeetCode_878._ N]  
[LeetCode\_容斥原理\_二分搜索\_中等\_1201.丑数 III][LeetCode_1201._ III]

## 3.代码实现（Java） ##

//思路1————因式分解
    class Solution {
        
        public boolean isUgly(int n) {
        
            if (n <= 0) {
        
                return false;
            }
            int[] factors = {
        2, 3, 5};
            for (int i = 0; i < factors.length; i++) {
        
                while (n % factors[i] == 0) {
        
                    n /= factors[i];
                }
            }
            return n == 1;
        }
    }

[LeetCode_264._ II]: https://blog.csdn.net/weixin_43004044/article/details/125969827
[LeetCode_313.]: https://blog.csdn.net/weixin_43004044/article/details/126074560
[LeetCode_878._ N]: https://blog.csdn.net/weixin_43004044/article/details/127976245
[LeetCode_1201._ III]: https://blog.csdn.net/weixin_43004044/article/details/129331211