Q136: Ugly Numbers

 

Ugly Number的定義為：該數之質因數必須為 2, 3 或 5

當然了，依照慣例，1 也算是 Ugly Number。

在此列舉一串數列：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15

這些就是前 11 個 Ugly Numbers。

請寫一個程式求出第1500個Ugly Number。

 

Input

　

No input

　

Output

　

The 1500'th ugly number is <number>.

 

Attention: Your program must be smart enough to solve this problem in 30 seconds. If your program is not so efficient, it may take much time to run. Please be patient.