LeetCode 263. 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].
描述
編寫一個程序判斷給定的數(shù)是否為丑數(shù)扮碧。
丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。
示例 1:
輸入: 6
輸出: true
解釋: 6 = 2 × 3
示例 2:
輸入: 8
輸出: true
解釋: 8 = 2 × 2 × 2
示例 3:
輸入: 14
輸出: false
解釋: 14 不是丑數(shù)溪食，因?yàn)樗肆硗庖粋€質(zhì)因數(shù) 7附迷。
說明：
1 是丑數(shù)践图。
輸入不會超過 32 位有符號整數(shù)的范圍: [?231, 231 ? 1]。
思路
- 根據(jù)題意丑數(shù)一定可以寫成
- 我們依次從給定的數(shù)字中去除因子2萤衰，3抚官，5 如果給定的數(shù)符合丑數(shù)的條件，那么最后剩下的數(shù)字一定是1,如果不是1桩砰，說明給定的數(shù)字不是丑數(shù).
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-02-03 09:30:18
# @Last Modified by: 何睿
# @Last Modified time: 2019-02-03 10:05:52
class Solution:
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0: return False
for factor in [2, 3, 5]:
# 用給定的數(shù)模上給定的因子拓春，如果結(jié)果為0說明還能從
# 給定的數(shù)字中至少分解出一個當(dāng)前因子
# 如果不為零，我們用當(dāng)前的數(shù)給下一個因子取模
while not num % factor:
num /= factor
# 如果是丑數(shù)亚隅，那么最后的結(jié)果一定是1
if num == 1: return True
return False
源代碼文件在這里.
?本文首發(fā)于何睿的博客硼莽，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源煮纵，作者信息和本聲明.
