题目描述

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

丑数 就是只包含质因数 2、3 和5 的正整数。

示例

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 8
输出：true
解释：8 = 2 × 2 × 2

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 

示例 4：

输入：n = 1
输出：true
解释：1 通常被视为丑数

提示：

−231-2^{31}−231 <= n <= 2312^{31}231 - 1

题目分析

来，我们上一节数学课，学学啥是丑数。

丑数 就是只包含质因数 2、3 和5 的正整数。

那什么又是质因数呢？

定义如下：

质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。

明白一点了，再看示例，恩，清晰很多了。

简单来说：

我把可以对输入的整数 n 反复除以 2,3,5，直到 n 不再包含质因数 2,3,5为止。

如果剩下的数等于 1，则说明 n 不包含其他质因数，就是丑数；

如果剩下的数不等于 1，说明 n 包含其他质因数，不是丑数。

思路讲解

1. 根据丑数的定义我们可以知道0和负数一定不是丑数
   
2. 循环遍历，将输入值n循环除以2、3、5，如果剩下的数为1，就是丑数
   
3. 否则就不是丑数

AC代码

var factors = []int{2, 3, 5}
func isUgly(n int) bool {
    if n <= 0 {
        return false
    }
    for _, f := range factors {
        for n%f == 0 {
            n /= f
        }
    }
    return n == 1
}

运行结果