/*
定义:丑数是指不能被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<<".
";//输出第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;
}