“丑数”指只包含质因数 2、3 和 5 的正整数。请寻找[2,50]范围的所有丑数。
时间: 2024-05-05 14:17:25 浏览: 79
首先,我们可以把 1 看作是第一个丑数。然后,我们从小到大依次生成丑数。具体做法如下:
1. 定义一个数组 ugly,用来存储生成的丑数。
2. 定义三个指针 p2、p3 和 p5,分别指向数组 ugly 中下一个乘以 2、3 和 5 的丑数的位置。初始时,p2、p3 和 p5 都指向第一个位置,即 1。
3. 从第二个位置开始,依次计算数组中的每一个丑数。具体步骤如下:
1. 计算下一个丑数,即 min(ugly[p2] * 2, ugly[p3] * 3, ugly[p5] * 5)。
2. 如果这个数等于 ugly[p2] * 2,说明下一个丑数是通过乘以 2 得到的,因此将 p2 加 1。
3. 如果这个数等于 ugly[p3] * 3,说明下一个丑数是通过乘以 3 得到的,因此将 p3 加 1。
4. 如果这个数等于 ugly[p5] * 5,说明下一个丑数是通过乘以 5 得到的,因此将 p5 加 1。
5. 将计算得到的下一个丑数加入数组 ugly 中。
4. 当数组中的丑数数量达到要求时,停止计算。
最终,数组 ugly 中存储的就是所有的丑数。下面是 Python 代码实现:
```python
def get_ugly_numbers(n):
if n <= 0:
return []
# 定义一个数组 ugly,用来存储生成的丑数
ugly = [1]
# 定义三个指针 p2、p3 和 p5,分别指向数组 ugly 中下一个乘以 2、3 和 5 的丑数的位置
p2, p3, p5 = 0, 0, 0
# 从第二个位置开始,依次计算数组中的每一个丑数
while len(ugly) < n:
# 计算下一个丑数,即 min(ugly[p2] * 2, ugly[p3] * 3, ugly[p5] * 5)
next_ugly = min(ugly[p2] * 2, ugly[p3] * 3, ugly[p5] * 5)
# 如果这个数等于 ugly[p2] * 2,说明下一个丑数是通过乘以 2 得到的,因此将 p2 加 1
if next_ugly == ugly[p2] * 2:
p2 += 1
# 如果这个数等于 ugly[p3] * 3,说明下一个丑数是通过乘以 3 得到的,因此将 p3 加 1
if next_ugly == ugly[p3] * 3:
p3 += 1
# 如果这个数等于 ugly[p5] * 5,说明下一个丑数是通过乘以 5 得到的,因此将 p5 加 1
if next_ugly == ugly[p5] * 5:
p5 += 1
# 将计算得到的下一个丑数加入数组 ugly 中
ugly.append(next_ugly)
return ugly
# 输出 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50]
print(get_ugly_numbers(24))
```
阅读全文