> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/shu-xue/263-chou-shu.md).

# \[263]\[简单]\[回溯] 丑数

## 题目描述

[263. 丑数](https://leetcode-cn.com/problems/ugly-number/)

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

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

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

示例 2:

```
输入: 8
输出: true
解释: 8 = 2 × 2 × 2
```

示例 3:

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

说明：

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

## 解题思路

回溯即可. 不停地除以2, 3, 5因子, 直到无法整除(回溯停止条件), 为1则为丑数, 不唯一说明有别的质数, 不是丑数.

递归版本如下:

```python
class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1:
            return False

        def is_ugly(number):
            if number == 1:
                return True

            cond2, cond3, cond5 = False, False, False
            if number % 2 == 0:
                cond2 = is_ugly(number // 2)
            if number % 3 == 0:
                cond3 = is_ugly(number // 3)
            if number % 5 == 0:
                cond5 = is_ugly(number // 5)
            return cond2 or cond3 or cond5
        return is_ugly(num)
```

但递归的效率低, 原因是做了很多重复的除法计算. 例如6对2, 3可整除, 在2和3处都进行了递归, 算了两遍. 优化的方法是使用迭代, 整除完之后, 就判断结果是否为丑数即可.

```python
class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1:
            return False

        while num > 1:
            if num % 2 == 0:
                num //= 2
            elif num % 3 == 0:
                num //= 3
            elif num % 5 == 0:
                num //= 5
            else:
                return False
        return True
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/shu-xue/263-chou-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.