LeetCode 263 Ugly Number

翻譯

寫一個程序來檢查給定的數字是否是丑數（Ugly number）。

丑數是一個正數，它的質因子只包括2、3、5。

例如，6、8是丑數，而因為包含了7這個因子，所以14不是丑數。

請注意，1通常被視為一個丑數。

原文

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

分析

遇到對題意不是很明朗的題目，我通常的做法是先寫一段明知是錯的方法去驗證一番。

比如我一開始試了一下，發現4是丑數：2 X 2 X 1，請注意這裡的1，請注意題目中特意提到了1是個丑數。那麼很自然就有這樣一行：

if(num == 1) return true;

這樣代碼的用處還有一個，下面會接著講。因為說了丑數是正數，所以0不是：

if(num == 0) return false;

回到上面的例子，4，我們可以讓它除一次2，但接著它還能除以一個2，顯然，這需要遞歸。如果是8的話，就要除以3次，最後的因子為1，返回真。

而對於14，除以2之後為7，但7對於2、3、5取余均不為0；同樣的，如果是28，會除以兩次2，最後同樣的結果。

OK，回到0和1，之所以它們倆如此重要，是因為要作為遞歸的終止條件。顯然，1應該是返回true，0返回false，但是最終如果不能被整除直接是一個return false，那麼能不能合並起來以至於不判斷num是否為0呢？也不能，因為這樣就會造成死循環，0除以任何數仍然為0。

於是這道題就解出來了。

代碼

class Solution {
public:
    bool isUgly(int num) {
        if (num == 0) return false;
        else if (num == 1) return true;
        else if (num % 2 == 0)
            return isUgly(num / 2);
        else if (num % 3 == 0)
            return isUgly(num / 3);
        else if (num % 5 == 0)
            return isUgly(num / 5);
        else return false;
    }
};