标签: 数学
难度: Easy
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3
示例 2：
输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3：
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
提示：
-231 <= n <= 231 - 1运行时间: 16 ms
内存: 16.0 MB
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
return n == 1
该题解的思路是对给定的整数n进行因数分解，看其是否只包含2、3、5这三个质因数。具体做法是，先判断n是否小于等于0，如果是则直接返回False。然后通过while循环，不断地将n分别除以2、3、5，直到不再包含这三个因数。最后判断n是否等于1，如果等于1则说明n只包含2、3、5三个质因数，是丑数，否则不是丑数。
时间复杂度: O(log(n))
空间复杂度: O(1)
class Solution:
def isUgly(self, n: int) -> bool:
# 特判，如果n小于等于0，直接返回False
if n <= 0:
return False
# 循环除以2，直到不再包含因数2
while n % 2 == 0:
n //= 2
# 循环除以3，直到不再包含因数3
while n % 3 == 0:
n //= 3
# 循环除以5，直到不再包含因数5
while n % 5 == 0:
n //= 5
# 如果最终n等于1，说明只包含2、3、5三个质因数，是丑数，否则不是丑数
return n == 1
在算法中首先判断n是否小于等于0是因为丑数定义仅适用于正整数。丑数是只包含质因数2、3、5的正整数。因此，非正整数（如负数和零）不符合丑数的定义，算法首先排除这些情况以简化后续处理。特别地，当n等于0时，按照丑数的定义，0不包含任何质因数，也不是正数，因此不是丑数。这个判断有助于直接返回正确结果，避免对0进行不必要的质因数分解操作，从而提高算法的效率和准确性。
如果在不断除以2、3、5后，最终n不等于1，这说明在n中仍然包含其他非2、3、5的质因数。这表示n包含至少一个其他质因数，如7、11、13等，这些不是2、3、5的质因数。因此，这样的n不是丑数。这种情形显示了算法的有效性，即能够通过分解和检查剩余的n值来确定是否存在不符合条件的其他质因数。
该算法在处理非常大的n值时，计算效率主要取决于n包含的2、3、5的因数个数。如果n是一个较大的数且主要由2、3、5组成，那么算法会较快地通过除法运算将n减小至1。但如果n包含大量其他质因数或者非常大的质因数（如大素数），则每次除法只减少一小部分，效率会下降。针对特定大小的n，优化的可能性包括使用更高效的数学方法预先判断n的质因数特性，或者在确认n包含大质因数时提前终止计算。
在while循环中不断除以2、3、5的逻辑是通过不停地除去n中的这些因数，直到不能再被这些数整除。这个过程基于整数除法的性质：每次除以一个数，如果n能整除这个数，则该因数会被完全去除，直到无法再整除指示n中不再包含该因数。因此，当无法继续除以2、3、5时，说明n已经不包含这些因数。这种方法是有效的，因为它确保了每次循环都彻底除掉一个因数，直到它不再存在于n中。