题目描述

写程序判断给出的数是不是“丑数”(ugly number)，“丑数”定义为：若一个正整数，它的质因数集合中不包含除了2、3、5以外的数，那么这个数是“丑数”。

样例

输入：6
输出：true
说明：6=2*3，满足条件

输入：14
输出：false
说明：14=2*7，有质因数7，不满足条件

算法1

$O(log(n))$

将这个正整数不断除以2、3、5这三个质数直到不能继续整除2、3、5为止，如果这个数是“丑数”，那么最后会剩下1，否则如果这个数质因数还包含2、3、5以外的质数，那么最后会剩下其他的质因数，所以通过判断最后剩下的值是不是1即可判断该数是否为“丑数”。
注意题目给出了输入范围为$[-2^{31}, 2^{31}-1]$，说明在int型范围内，并且注意“丑数”必须为正整数，当输入不是正整数则直接返回false即可。

时间复杂度分析：需要除以log(n)次的2、3和5，所以复杂度为$O(log(n))$。

C++ 代码

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0)
            return false;
        while (num % 5 == 0)
            num = num / 5;
        while (num % 3 == 0)
            num = num / 3;
        while (num % 2 == 0)
            num = num / 2;
        return num == 1;
    }
};