一、问题描述
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 **丑数 ** 。如果是，返回 true ；否则，返回 false 。
题目链接：丑数 l
二、题目要求
样例 1
输入： n = 6 输出： true 解释： 6 = 2 × 3
样例 2
输入： n = 1 输出： true 解释： 1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。
考察
贪心、模拟 建议用时15~35min
三、问题分析
这一题其实简单判断就行了，比如我一开始的想法就是看看这个数字能否被若干个 2 3 5相乘得到，如果可以的话，就返回true，否则返回false。
我最初写的代码有点长，但很容易理解。
后来发现，这种方法还可以优化，三重循环嵌套太差劲了。
优化
思想还是这一个思想，只不过是把三重循环分成各自独立的。
n是2的倍数，进入循环/2n是3的倍数，进入循环/3n是5的倍数，进入循环/5
四、编码实现
1.初始版本
classSolution { public: boolisUgly(intn) {//（●＞ω＜●）inti,j,k,a,b,c;//初始化数据for(i=0;pow(2,i)<=n;i++)//判断有几个2 { a=pow(2,i); for(j=0;pow(3,j)<=n/a;j++)//判断有几个3 { b=pow(3,j); for(k=0;pow(5,k)<=n/(a*b);k++)//判断有几个5 { c=pow(5,k); if(a*b*c==n)//如果能够构成，返回truereturntrue; } } } returnfalse;//不能构成，返回false } };
2.优化后
classSolution { public: boolisUgly(intn) { if(n<1) returnfalse;//n为0,返回falsewhile(n%2==0) n=n/2;//进入2循环while(n%3==0) n=n/3;//进入3循环while(n%5==0) n=n/5;//进入5循环if(n==1)//结果是1，那么肯定能被2 3 5组成returntrue; else//否则不能returnfalse; } };
五、测试结果
优化后的执行用时明显低了。
