育华学校第N个丑数问题

难度评分: 1500 (CodeForces标准)

题目描述

丑数是指只包含质因数 2、3 和 5 的正整数。育华学校的算法竞赛中，需要你找出第 $n$ 个丑数。

例如，1 是第一个丑数，因为它没有质因数。接下来的丑数依次是 2、3、4、5、6、8 等。

输入格式

输入一个正整数 $n$，表示需要找出的第 $n$ 个丑数。

输出格式

输出第 $n$ 个丑数。

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

10

输出 #2

12

输入输出样例 #3

输入 #3

15

输出 #3

24

说明/提示

样例 1 中，第一个丑数是 1，所以输出 1。 样例 2 中，第 10 个丑数是 12，所以输出 12。 样例 3 中，第 15 个丑数是 24，所以输出 24。

数据范围：

• 30%的数据：$n \leq 100$。
• 60%的数据：$n \leq 1000$。
• 100%的数据：$n \leq 10000$。