UVA136 醜數 Ugly Numbers

題意

題意描述：醜數是一些因子隻有2,3,5的數。數列1,2,3,4,5,6,8,9,10,12,15……寫出了從小到大的前11個醜數，1屬于醜數。現在請你編寫程式，找出第1500個醜數是什麼。

輸出案例

The 1500'th ugly number is <number>.      

參考代碼

#include<iostream>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;//這個題得使用Long Long類型，防止越界。
priority_queue<ll, vector<ll>,greater<ll> > pq;//數越小優先級越大。
set<ll> s;
ll x;
int arr[3] = { 2,3,5 };
int main() {
  s.insert(1);//從第一個數開始尋找
  pq.push(1);
  for (int i = 1; ; i++) {
    x = pq.top();//每次彈出一個最小的數x，往後尋找醜數：其中2x,3x,5x也是醜數。
    pq.pop();
    if (i == 1500) {//當彈出1500個時候，剛剛彈出的那個就是所求  
      cout <<"The 1500'th ugly number is "<< x <<"."<< endl;
      break;
    }
    for (int j = 0; j < 3; j++) {
      if (!s.count(arr[j] * x)) {//一個數可能有多種生成方式，如果已經被其他方式生成過了，則該種生成忽略。
        s.insert(arr[j] * x);
        pq.push(arr[j] * x);
      }
    }
  }
  return 0;
}