/*
定义:丑数是指不能被2,3,5以外的其他素数整除的数.
问题:把丑数从小到大排列起来,结果如下 1 2 3 5 6 8 9 10 12 15 求第1500个丑数
解题思路:丑数的2,3,5倍仍然是丑数(排除重复的)
*/
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;
typedef long long LL;//定义long long 类型的别名
const int coeff[3]={2,3,5};//定义基础数组
int main(){
    priority_queue<LL,vector<LL>,greater<LL> > pq;//定义优先队列这个是越小的整数优先级越大的优先队列
    set<LL> s;//定义集合 排重
    pq.push(1);//进入队列
    s.insert(1);//插入集合
    for(int i=1;;i++){

        LL x=pq.top();//获取到队列第一个元素(因为是按最小优先的原则排序的)
        pq.pop();//第一元素出队列 所以 第1500个丑数就是pop1499后的那个元素
        if(i==1500){
            cout<<"The 1500‘th ugly number is "<<x<<".\n";//输出第1500个丑数
            break;//跳出循环
        }
        for(int j=0;j<3;j++){
            LL x2=x*coeff[j];//x2是2 3 5的倍数
            //判断集合中有没有x2 若没有进入if中
            if(!s.count(x2)){
                s.insert(x2);//插入到s集合中
                pq.push(x2);//进队列
            }
        }
    }
    return 0;
}

c++ 丑数