丑数

问题描述（来源于LeetCode）

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isUgly(self, n: int) -> bool:
        if n<=0:
            return False
        while 1:
            if n%2 !=0:
                break
            n=n//2
        while 1:
            if n%3 !=0:
                break
            n=n//3
        while 1:
            if n%5 !=0:
                break
            n=n//5
        if n==1:
            return True
        else:
            return False

复杂度分析

  • 时间复杂度O(Logn)O(Logn)
  • 空间复杂度O(1)O(1)