[LeetCode] 263. 丑数

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

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

示例 1：

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

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数。

示例 3：

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

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

思路:

最暴力的做法当然是直接循环去除 2、3 和 5，最终剩下1那就是丑数了。

AC代码:

class Solution {
public:
    bool isUgly(int num) {
        if(num<1)
        {
            return false;
        }
        else
        {
            while(num%5 == 0 && num !=0)
            {
                num = num / 5;
            }
            while(num%3 == 0 && num !=0)
            {
                num = num / 3;
            }
            while(num%2 == 0 && num !=0)
            {
                num = num / 2;
            }
            if(num == 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
};Code language: C++ (cpp)

还有一种素数筛的做法， 即查表：

class Solution {
    struct UglyData {
        vector<int> list;
        unordered_set<int> set;
        
        UglyData() {
            for (long a = 1; a <= INT_MAX; a *= 2)
                for (long b = a; b <= INT_MAX; b *= 3)
                    for (long c = b; c <= INT_MAX; c *= 5)
                        list.push_back((int)c);
            set.insert(list.begin(), list.end());
        }
    };
    
    inline static const UglyData data;
    
public:
    bool isUgly(int n) {
        return n > 0 && data.set.count(n);
    }
};Code language: C++ (cpp)