---
# System prepended metadata

title: UVa 136 - Ugly Numbers

---

# UVa 136 - Ugly Numbers

---
# 題目大意
輸出第1500個質因數只有2、3、5的數

---
# 題解
用$set$紀錄已經出現過的數，用$priority-queue$找下一個數。用$priority-queue$是為了保證覆蓋到所有由2、3、5組成的數。

---
```=C++
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sec second
#define pr pair<int,int>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll t ,n ,m ,cnt ,num[3]={2,3,5} ,now;
int main() 
{
	priority_queue<ll ,vector<ll> ,greater<ll> > pq;
	pq.push(1);
	set<ll> st;
	st.insert(1);
	for(int i=1 ;i<=1500 ;i++)
	{
		now = pq.top(); pq.pop();
		for(int j=0 ;j<3 ;j++) if(!st.count(now*num[j]))
			st.insert(now*num[j]) ,pq.push(now*num[j]);
	}
	printf("The 1500'th ugly number is %lld.\n",now);
	return 0;	
}
```