###### tags: `leetcode` `easy` `math`
# [263. Ugly Number](https://leetcode.com/problems/ugly-number/)

## Description

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

### 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.

## Constraints:

- $-2^{31}$ $\leq$ n $\leq$ $2^{31}$ - 1

## Code

- C

bool isUgly(int n){
    if ((n == 1) || (n == 2) || (n == 3) || (n == 5))
        return true;
    for (int i = 2;i <= ceil(sqrt(n));i ++)
        if(n%i == 0)
            return isUgly(i) & isUgly(n / i);
    
    return false;
}

- Python

from operator import truediv

def divideBy(n, div):
    while n%div == 0:
        n = n/div
        if n == 1:
            return 1
    return n

class Solution(object):
    def isUgly(self, n):
        if n <= 0:
            return False
        # tmp = divideBy(n, 2)
        # if tmp == 1:
        #     return True
        # tmp = divideBy(tmp, 3)
        # if tmp == 1:
        #     return True
        # tmp = divideBy(tmp, 5)
        # if tmp == 1:
        #     return  True
        # return False

        return divideBy(divideBy(divideBy(n, 2), 3), 5) == 1

## Complexity

|Space |Time |
|- |- |
|$O(1)$ |$O(log(n))$|

## Result

### C

- Runtime: 19 ms, 5.24%
- Memory usage: 5.6 MB, 26.22%

### Python

- Runtime: 53 ms, 69.42%
- Memory usage: 14 MB, 12.19%