题目描述

写一个程序检查一个给定的数字是否为 ugly 数字。

ugly 数字为 正整数 且其质因子仅包含 2, 3, 5。

注意

• 1 是 ugly 数字。
• 输入的数字为 32 位有符号整数 $[-2^{31}, 2^{31}-1]$。

样例

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

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

输出：14
输出：false 
解释：14 不是 ugly 数字，因为它包含质因子 7。

算法

(模拟) $O(\log n)$

1. 如果 num <= 0，则返回 false。
2. 然后用取余判断 num 是否包含 2, 3, 5，通过除法去掉这些质因子。
3. 最后判断 num 是否为 1，如果不为 1 则说明含有其它质因子。

时间复杂度

• 最坏情况下时间复杂度为 num 以 2 为底的对数，故为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0)
            return false;

        while (num % 2 == 0)
            num /= 2;

        while (num % 3 == 0)
            num /= 3;

        while (num % 5 == 0)
            num /= 5;

        return num == 1;
    }
};