Python丑数算法详解：从暴力到动态规划的优雅实践263

在编程世界中，有些数字因其独特的数学性质而被赋予了特定的名称，"丑数"（Ugly Number）便是其中之一。这个概念不仅在面试中频繁出现，也是理解动态规划（Dynamic Programming）和优先队列（Priority Queue）等算法思想的绝佳案例。作为一名专业的程序员，我将带您深入探讨丑数的定义、不同求解方法及其Python实现，从直观的暴力破解到高效的动态规划，再到巧妙的堆优化，力求为您呈现一份全面且深入的指南。

什么是丑数？

丑数，顾名思义，并不是指长得不好看的数字，而是特指那些其所有素因子都只包含2、3或5的正整数。根据定义，1通常被认为是第一个丑数，因为它没有任何素因子（或者可以认为其素因子集合为空集，满足条件）。

让我们来看一些例子：
1：第一个丑数。
2：素因子为2。
3：素因子为3。
4：素因子为2, 2 (2^2)。
5：素因子为5。
6：素因子为2, 3 (2*3)。
8：素因子为2, 2, 2 (2^3)。
9：素因子为3, 3 (3^2)。
10：素因子为2, 5 (2*5)。
12：素因子为2, 2, 3 (2^2*3)。

那么，哪些不是丑数呢？
7：素因子为7。
14：素因子为2, 7 (包含7)。
13：素因子为13。
17：素因子为17。

理解丑数的定义是解决问题的基础。我们的目标通常是找到第N个丑数，或者生成前N个丑数的列表。

方法一：暴力破解（Brute Force）

最直观的方法是逐个检查每个正整数，判断它是否是丑数。如果是，就计数，直到找到第N个丑数为止。

判断一个数是否为丑数

要判断一个数num是否为丑数，我们可以不断地将其除以2、3、5，直到它不能再被这些因子整除。如果最终结果变为1，那么它就是丑数；否则，就不是。def is_ugly(num: int) -> bool:
"""
判断一个正整数是否为丑数
"""
if num int:
"""
通过暴力破解查找第N个丑数
"""
if n int:
"""
使用动态规划查找第N个丑数
"""
if n int:
"""
使用最小堆查找第N个丑数
"""
if n

2025-11-24

下一篇：Python 文件上传脚本深度指南：从requests库到高级实践与安全考量