###### tags: `Math`
# Leetcode 263. Ugly Number

1. 問題描述
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors
are limited to 2, 3, and 5.

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

2. Input的限制
* -2^31^ <= n <= 2^31^ - 1.

3. 思考流程
* Maths
此題定義了，一個數若只擁有 2, 3, 5 為質因數，就是所謂的 ugly number。因此，我們依照定義和題目給的限制，如果是負數的話，則此數不是 ugly number。如果是正數，則我們將此數一直除 2，直到產生餘數為止，接著依序對 3 和 5 做一樣的除法程序，最後剩下來的數如果不等於 1，則此數不是ugly number。<br>

因為主要的迴圈在除 2, 3, 5 上，一個數 N 如果最多能被 2 除 k 次，則 2^k^ <= N。取 log 後，k <= log~2~N，故 time complexity 是 O(logN)。而 space complexity 是 O(1)。

Time Complexity: O(logN); Space Complexity: O(1)
4. 測試
* test 1
Input: n = -3
Output: false
* test 2
Input: n = 30
Output: true
* test 3
Input: n = 42
Output: false