# 0263. 丑數 ## 題目地址(263. 丑數) <https://leetcode-cn.com/problems/ugly-number/> ## 題目描述 ``` <pre class="calibre18">``` 編寫一個程序判斷給定的數是否為丑數。 丑數就是只包含質因數 2, 3, 5 的正整數。 示例 1: 輸入: 6 輸出: true 解釋: 6 = 2 × 3 示例 2: 輸入: 8 輸出: true 解釋: 8 = 2 × 2 × 2 示例 3: 輸入: 14 輸出: false 解釋: 14 不是丑數，因為它包含了另外一個質因數 7。 說明： 1 是丑數。 輸入不會超過 32 位有符號整數的范圍: [?231, 231 ? 1]。 ``` ``` ## 前置知識 - 數學 - 因數分解 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 題目要求給定一個數字，判斷是否為“丑陋數”(ugly number), 丑陋數是指只包含質因子2, 3, 5的正整數。  根據定義，我們將給定數字除以2、3、5(順序無所謂)，直到無法整除。 如果得到1，說明是所有因子都是2或3或5，如果不是1，則不是丑陋數。 這就好像我們判斷一個數字是否為n(n為大于1的正整數)的冪次方一樣，我們只需要 不斷除以n，直到無法整除，如果得到1，那么就是n的冪次方。 這道題的不同在于 它不再是某一個數字的冪次方，而是三個數字（2，3，5），不過解題思路還是一樣的。 轉化為代碼可以是： ``` <pre class="calibre18">``` <span class="hljs-keyword">while</span>(num % <span class="hljs-params">2</span> === <span class="hljs-params">0</span>) num = num / <span class="hljs-params">2</span>; <span class="hljs-keyword">while</span>(num % <span class="hljs-params">3</span> === <span class="hljs-params">0</span>) num = num / <span class="hljs-params">3</span>; <span class="hljs-keyword">while</span>(num % <span class="hljs-params">5</span> === <span class="hljs-params">0</span>) num = num / <span class="hljs-params">5</span>; <span class="hljs-keyword">return</span> num === <span class="hljs-params">1</span>; ``` ``` > 我下方給出的代碼是用了遞歸實現，只是給大家看下不同的寫法而已。 ## 關鍵點 - 數論 - 因數分解 ## 代碼 - 語言支持：JS, C++, Java, Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=263 lang=javascript * * [263] Ugly Number */</span> <span class="hljs-title">/** * @param {number} num * @return {boolean} */</span> <span class="hljs-keyword">var</span> isUgly = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">num</span>) </span>{ <span class="hljs-title">// TAG: 數論</span> <span class="hljs-keyword">if</span> (num <= <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (num === <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">const</span> list = [<span class="hljs-params">2</span>, <span class="hljs-params">3</span>, <span class="hljs-params">5</span>]; <span class="hljs-keyword">if</span> (list.includes(num)) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i <span class="hljs-keyword">of</span> list) { <span class="hljs-keyword">if</span> (num % i === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> isUgly(<span class="hljs-params">Math</span>.floor(num / i)); } <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; }; ``` ``` **復雜度分析** - 時間復雜度：O(logN)O(logN)O(logN) - 空間復雜度：O(logN)O(logN)O(logN) C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isUgly</span><span class="hljs-params">(<span class="hljs-keyword">int</span> num)</span> </span>{ <span class="hljs-keyword">int</span> ugly[] = {<span class="hljs-params">2</span>,<span class="hljs-params">3</span>,<span class="hljs-params">5</span>}; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> u : ugly) { <span class="hljs-keyword">while</span>(num%u==<span class="hljs-params">0</span> && num%u < num) { num/=u; } } <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span>; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isUgly</span><span class="hljs-params">(<span class="hljs-keyword">int</span> num)</span> </span>{ <span class="hljs-keyword">int</span> [] ugly = {<span class="hljs-params">2</span>,<span class="hljs-params">3</span>,<span class="hljs-params">5</span>}; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> u : ugly) { <span class="hljs-keyword">while</span>(num%u==<span class="hljs-params">0</span> && num%u < num) { num/=u; } } <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span>; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># 非遞歸寫法</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isUgly</span><span class="hljs-params">(self, num: int)</span> -> bool:</span> <span class="hljs-keyword">if</span> num <= <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> (<span class="hljs-params">2</span>, <span class="hljs-params">3</span>, <span class="hljs-params">5</span>): <span class="hljs-keyword">while</span> num % i == <span class="hljs-params">0</span>: num /= i <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span> ``` ``` **復雜度分析** - 時間復雜度：O(logN)O(logN)O(logN) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。