丑数（优先队列问题）

丑数是指不能被2，3，5以外的其他素数整除的数。把丑数从小到大排列起来，结果如
下：
1,2,3,4,5,6,8,9,10,12,15,…
求第1500个丑数。

【分析】
已知1，2，3，5必定是丑数，而且如果x是丑数，那么2x、3x、4x也一定是丑数。那么我们可以设置一个优先队列，循环出队然后把2x、3x、5x入队，循环到1500次终止。

#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int coeff[3] = {2, 3, 5};

int main() {
	priority_queue<LL, vector<LL>, greater<LL> > pq; //创建一个优先队列，越小的整数优先级越大 
	set<LL> s; //创建一个集合s ，作用是防止重复 
	pq.push(1); // 1进队 
	s.insert(1); // 1插入集合 
	
	for(int i = 1; ; i++) { 
		LL x = pq.top(); // 取队首 
		pq.pop() ; // 队首出队 
		if(i == 1500) {
			cout << "第1500个丑数是" << x << endl;
			break; 
		}
		for(int j = 0; j < 3; j++) { // 把出栈的元素分别×2，3，5得到的还是丑数 
			LL x2 = x * coeff[j]; 
			if(!s.count(x2))  { 
				s.insert(x2); pq.push(x2); 
			}
		}
	}
	

	
	return 0;
}