题目描述

[EN | CN]

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 235正整数

示例 1:

1
2
3
输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

1
2
3
输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

1
2
3
输入: 14
输出: false
解释: 14 不是丑数,因为它包含了另外一个质因数 7。

说明:

  1. 1 是丑数。
  2. 输入不会超过 32 位有符号整数的范围:$[−2^{31}, 2^{31} − 1]$。

解法 1:直接法

直接按照定义实现即可。

复杂度分析略。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def isUgly(self, num: int) -> bool:
        while num % 2 == 0:
            num /= 2
        while num % 3 == 0:
            num /= 3
        while num % 5 == 0:
            num /= 5
        return num == 1
  • 执行用时:40 ms,在所有 Python3 提交中击败了 77.14% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.56% 的用户。