leetcode-263-Ugly Number
leetcode-263-Ugly Number
题目描述：
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include?2, 3, 5. For example,?6, 8?are ugly while?14?is not ugly since it includes another prime factor?7.
Note:
1?is typically treated as an ugly number.- Input is within the 32-bit signed integer range.
要完成的函数：
bool isUgly(int num)?
说明：
1、这道题目不难理解。一个只包括2、3、5的素数因子的正数是ugly number，1特别处理为ugly number。输入是一个32位的有符号型整数。
2、首先我们在想这道题目能不能不断地整除2、整除3、整除5，最后等于1，就判断是一个ugly number。如果整除完还是不等于1，就不是ugly number。
但题目中说的是素数因子，那要是包含一些非素数因子，比如偶数、奇数中的合数呢？
偶数不用说，总是能整除2的。奇数中的合数，也是由素数相乘而构成的，比如15=3*5，27=3*3*3，21=3*7，所以奇数中的合数也能不断地整除2、整除3、整除5，然后看是不是最终等于1来判断。
所以这道题目，按照我们最开始的思路，是可以处理的。
代码如下：
bool isUgly(int num)
{
if(num<=0)//边界条件处理
return false;
while(num%2==0) num>>=1;//位操作更加便于计算机处理，且更快
while(num%3==0) num/=3;
while(num%5==0) num/=5;
return num==1;//如果num==1，那么直接返回true
}实测6ms，beats 77.79% of cpp submissions。
3、受到昨天那道“判断一个数是不是2的整数次幂”的题目的启发，笔者在想能不能找到一个最大的整数，它包含了2、3、5的因子，然后判断这个最大整数能否整除num，从而判断是不是ugly number。
但是这个最大整数必定是远远超过int型整数所能表示的范围，它需要30个2的因子（int型整数所能拥有最多的2因子），19个3的因子（int型整数所能拥有最多的3因子），13个5的因子（int型整数所能拥有最多的5因子）。
接着判断这个最大整数是否能整除num，就可以做出一个时间复杂度为O(1)的判断了，只需要做一次大数除法。
不过大数除法似乎本身时间复杂度也挺高的……可能到最后实际上还没有2中的做法快。
个人的一点想法。