丑数

题目：

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

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

题目分析：

根据丑数的定义可知负数和0一定不为丑数。

当n>0时，丑数n = 2^a * 3^b * 5^c ，其中a, b, c 都为自然数，特别当a ,b ,c 都为0时，n = 1 。

判断是否为整数就需要判断 n 是否满足上式条件。首先可以先判断 n 是否为正整数，是否含有质因数并且是否是1，然后不断除以3，5直到没有质因数3，5，如果n为丑数这时n = 2^a ，最后通过位运算快速判断是否为2的幂（利用位运算实现计算2的幂 – 星海博客），如果是2的幂那么n就为丑数，否则就不是丑数。

代码：

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

复杂度分析

空间复杂度：O(1)。

时间复杂度：O(logn)。有 O(logn) 个因子 3 和因子 5。