Ugly number

。題目假設

給一個數，判斷他是否為 ugly number，也就是因數只包含{2, 3, 5}

。重要問題

基礎數學運算

。直覺

與質因數分解有關

。解決方法可行性

質因數分解顯然不是這題想要的解法，而且也沒這麼複雜

既然要判斷 number 是不是2, 3, 5 的倍數，那就將 number 除這些數

如果有不是 {2, 3, 5} 的因數，那除下來一定會剩下 1，原因是我們要除 2

。解決方案

將 number 除2之後的餘數拿去除3，餘數再拿去除 5

。資料結構

無

。複雜度

O(n/{2,3,5})

。遇到的困難點、想錯的地方

我卡在不知道要怎麼實現「把 number 一直除 2之後再看看他除 3 是不是 0 ，再看看 5」

結果很簡單，就是先除以2，再直接除 3，再除 5

public boolean isUgly(int num) {
    if (num <= 0) return false;
    if (num == 1)
        return true;

    while (num >= 2 && num % 2 == 0) num /= 2;
    while (num >= 3 && num % 3 == 0) num /= 3;
    while (num >= 5 && num % 5 == 0) num /= 5;
    return num == 1;
}

Ugly number II