题目:
丑数是一些因子只有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、输出完应换行。

解题思路:
首先我们要找出数列的规律,我们仔细观察可以发现,任意数字x,他的丑数为x、2x、3x、5x,然后们通过一个最小堆形成的优先队列,每次取出最小元素,然后判断它的2x、3x、5x是否在队列中,如果不在那么就push()进优先队列,那么我们判断是否在队列中呢,熟悉set集合的同学,可以清楚知道,set不允许重复元素,并且set可以帮助我们排序,所以我们**用set集合去除重复元素!**最后整体利用for循环i从1开始,直到i=1500就可以判断第1500个丑数!

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;//需要注意,我们如果开int可能越界,后面的丑数可能很大。
const int coeff[3]= {2,3,5};
int main()
{
    priority_queue<LL,vector<LL>,greater<LL> >pq; //最小堆形成的优先队列
    set<int> s;//set帮助我们去除重复元素
    pq.push(1);
    s.insert(1);
    for(int i=1;; i++)
    {
        LL t=pq.top(); //每次拿出最小的丑数
        pq.pop();
        if(i==1500)
        {
            printf("The 1500'th ugly number is %d.\n",t);
            break;
        }

        for(int i=0; i<3; i++)
        {
            if(!s.count(t*coeff[i]))
            {
                s.insert(t*coeff[i]);
                pq.push(t*coeff[i]);
            }
        }
    }
    return 0;
}