丑数不丑——从一个简单定义，看清“有序生成”这件大事

丑数不丑

从一个简单定义，看清“有序生成”这件大事

一、先别急着写代码：什么是丑数？

我们先说一句大白话版定义：

丑数，就是只包含质因子 2、3、5 的正整数。

比如：

• 1（特殊地，也算）
• 2、3、4、5、6、8、9、10、12 …

而下面这些就不是：

• 7（有 7）
• 14（2 × 7）
• 21（3 × 7）

听起来是不是很简单？

但危险也恰恰藏在“太简单”里。

二、很多人第一反应就错了：暴力判断法

最常见的思路是：

从 1 开始，一个一个判断是不是丑数，直到找到第 n 个。

判断方法也很直觉：

defis_ugly(num