题意
题意描述：丑数是一些因子只有2,3,5的数。数列1,2,3,4,5,6,8,9,10,12,15……写出了从小到大的前11个丑数，1属于丑数。现在请你编写程序，找出第1500个丑数是什么。
没有输入
输出：The 1500’th ugly number is <…>.（<…>为你找到的第1500个丑数） 注意：<…>是你找到的数，输出中没有尖括号； 2、输出完应换行。
输出案例
The 1500'th ugly number is <number>.
参考代码
#include<iostream> #include<set> #include<queue> #include<vector> using namespace std; typedef long long ll;//这个题得使用Long Long类型，防止越界。 priority_queue<ll, vector<ll>,greater<ll> > pq;//数越小优先级越大。 set<ll> s; ll x; int arr[3] = { 2,3,5 }; int main() { s.insert(1);//从第一个数开始寻找 pq.push(1); for (int i = 1; ; i++) { x = pq.top();//每次弹出一个最小的数x，往后寻找丑数：其中2x,3x,5x也是丑数。 pq.pop(); if (i == 1500) {//当弹出1500个时候，刚刚弹出的那个就是所求 cout <<"The 1500'th ugly number is "<< x <<"."<< endl; break; } for (int j = 0; j < 3; j++) { if (!s.count(arr[j] * x)) {//一个数可能有多种生成方式，如果已经被其他方式生成过了，则该种生成忽略。 s.insert(arr[j] * x); pq.push(arr[j] * x); } } } return 0; }
