Example 24
丑数
题目概述：丑数就是只包含质因数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 。
解题思路：根据丑数的定义，00 和负整数一定不是丑数。
当n>0 时，若n 是丑数，则n 可以写成n = 2a * 3b * 5c的形式，其中a,b,c 都是非负整数。特别地，当a,b,c 都是0 时，n=1。
为判断n 是否满足上述形式，可以对n 反复除以2,3,5，直到n 不再包含质因数2,3,5。若剩下的数等于1，则说明n 不包含其他质因数，是丑数；否则，说明n 包含其他质因数，不是丑数。
解题步骤：是
1. 首先判断n是否小于等于0，若是，则直接返回false，否则继续向下执行。
2. 定义数组factors存储质因数2、3、5，用做后续反复除法中的除数。
3. 定义for循环，依次从数组中取出各个质因数，并用n反复除以该质因数，直至无法整除，再取出下一个质因数，重复该过程。
4. for循环结束后，即质因数被反复做除法后，此时n已经不包含质因数2、3、5，若此时n等于1，则说明除2、3、5外，原n不含其他质因数（不包含1），n是丑数，返回true，否则说明除以上三个数之外，还有其他质因数（不包含1），n不是丑数，返回false。
示例代码如下：
public class UglyNumber { /** * 丑数就是只包含质因数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 。 * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/ugly-number */ public static void main(String[] args) { UglyNumber un = new UglyNumber(); System.out.println(un.isUgly(6)); // true } /** * 官方 * * @param n * @return */ 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; } /** * 个人 * @param n * @return */ /*public boolean isUgly(int n) { if (n <= 0) return false; while (n % 2 == 0) { n = n / 2; } while (n % 3 == 0) { n = n / 3; } while (n % 5 == 0) { n = n / 5; } return n == 1; }*/ }
