[LeetCode] #263 - Ugly Number

주어진 문제는 아래와 같다.

난의도 : ★★☆☆☆

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.

Note:

1 is typically treated as an ugly number.
Input is within the 32-bit signed integer range: [−2^31, 2^31 − 1].

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

Output: true
Explanation: 8 = 2 × 2 × 2

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

분석하기

즉 입력받은 숫자가 소수(factors)이고 소인수(prime factors)가 2, 3, 5중에 하나이면 True 아니면 False 를 반환해주는 문제이다.

먼저 소수가 무엇인지 알아보면 나눠지는 수 즉 약수(divisor)가 1과 자기 자신인 수이다.
EX) 2, 3, 5, 7, 11, 13, 17

즉 2 부터 N - 1까지 순서대로 정수로 나눠서 떨어지는 수가 없으면 소수인데
이 문제의 경우 [2, 3, 5]를 순서대로 계속 나눠서 최종적으로 떨어지는 수가 1인경우 True를 반환하면 된다.

코드로 구현하기 (파이썬)

class Solution:
    def isUgly(self, num: 'int') -> 'bool':
        if num is 0 : return False
        for i in [2, 3, 5] :
            while num % i is 0:
                num = num // i
        return num is 1

시간 복잡도는 O(log n)이 되겠다.