263.ugly-number.md

题目地址

https://leetcode.com/problems/ugly-number/description/

题目描述

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.

Example 1:

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

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2
Example 3:

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

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

前置知识

• 因数分解

思路

题目要求给定一个数字，判断是否为“丑陋数”(ugly number), 丑陋数是指只包含质因子2, 3, 5的正整数。

根据定义，我们将给定数字除以2、3、5(顺序无所谓)，直到无法整除。 如果得到1，说明是所有因子都是2或3或5，如果不是1，则不是丑陋数。

这就好像我们判断一个数字是否为n(n为大于1的正整数)的幂次方一样，我们只需要 不断除以n，直到无法整除，如果得到1，那么就是n的幂次方。 这道题的不同在于 它不再是某一个数字的幂次方，而是三个数字（2，3，5），不过解题思路还是一样的。

转化为代码可以是：

  while(num % 2 === 0)   num = num / 2;
  while(num % 3 === 0)   num = num / 3;
  while(num % 5 === 0)   num = num / 5;

  return num === 1;

我下方给出的代码是用了递归实现，只是给大家看下不同的写法而已。

关键点

• 数论
• 因数分解

代码

• 语言支持：JS, Python

Javascript Code:

/*
 * @lc app=leetcode id=263 lang=javascript
 *
 * [263] Ugly Number
 */
/**
 * @param {number} num
 * @return {boolean}
 */
var isUgly = function(num) {
  // TAG: 数论
  if (num <= 0) return false;
  if (num === 1) return true;

  const list = [2, 3, 5];

  if (list.includes(num)) return true;

  for (let i of list) {
    if (num % i === 0) return isUgly(Math.floor(num / i));
  }
  return false;
};

Python Code:

# 非递归写法
class Solution:
    def isUgly(self, num: int) -> bool:
        if num <= 0:
            return False
        for i in (2, 3, 5):
            while num % i == 0:
                num /= i
        return num == 1