問(wèn)題描述
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 that 1 is typically treated as an ugly number.
補(bǔ)充說(shuō)明：
輸入一個(gè)數(shù)字，判斷這個(gè)數(shù)字是不是丑陋數(shù)苛预。何為丑陋數(shù)照雁，所謂的丑陋數(shù)就是如果一個(gè)數(shù)它的全部質(zhì)因數(shù)在集合2褂乍、 3拌汇、 5這三個(gè)數(shù)字組成的集合中蚯根，則這個(gè)數(shù)字是丑陋數(shù)驹止。
方案分析
- 要搞定這個(gè)問(wèn)題棵红，首先需要了解一個(gè)概念凶赁，叫做質(zhì)因數(shù)。這里有個(gè)鏈接講的特別生動(dòng)逆甜，筆者就不贅述了虱肄。prime factor。
- 看懂上面那個(gè)鏈接的內(nèi)容交煞，想必大家都有了思路了吧咏窿。這個(gè)問(wèn)題其實(shí)比求質(zhì)因數(shù)還簡(jiǎn)單。因?yàn)檫@個(gè)已經(jīng)限定了質(zhì)因數(shù)的集合了素征。上代碼翰灾，自己揣摩。
python實(shí)現(xiàn)
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num == 0:
return False
check_list = [2, 3, 5]
for i in check_list:
while(num % i == 0):
num /= i
if num == 1:
return True
return False
方案分析2
- 在OJ上看到了另外一個(gè)解決方案稚茅，這個(gè)更加粗暴。你不是說(shuō)質(zhì)因素只能包含這3個(gè)數(shù)字的子集嗎平斩？好亚享，就反復(fù)除以這3個(gè)數(shù)字，直到再無(wú)法進(jìn)行下去绘面。然后判斷最后的結(jié)果數(shù)字是否為1欺税。為1則表明只包含這3個(gè)數(shù)字的子集。
python實(shí)現(xiàn)2
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num == 0: return False
if num == 1: return True
while(num % 2 == 0):
num /= 2
while(num % 3 == 0):
num /= 3
while(num % 5 == 0):
num /= 5
return num == 1
