Python算法例35 丑数Ⅰ

1. 问题描述

丑数的定义是，只包含质因子2、3、5的正整数，例如6、8就是丑数，但14不是丑数，因为它包含了质因子7，本例将检测一个整数是不是丑数。

2. 问题示例

给出num=8，返回True；给出num=14，返回False。

3. 代码实现

使用简单的贪心算法来判断一个数是否为丑数

def isUgly(num):
    if num <= 0:
        return False
    while num % 2 == 0:
        num /= 2
    while num % 3 == 0:
        num /= 3
    while num % 5 == 0:
        num /= 5
    return num == 1
print(isUgly(14))

该算法通过将给定的数字不断除以2、3和5，直到无法再整除为止。如果最终得到的结果是1，则说明原始数字只包含质因子2、3和5，是丑数；否则，不是丑数。

这种贪心算法的思想是不断将数字变小，直到达到特定条件为止。它利用了丑数只包含质因子2、3和5的性质，通过排除其他质因子来判断一个数是否为丑数。

由于我们只需要对给定的数字进行有限次的除法操作，所以该算法的时间复杂度为，其中n是给定的数字。