題目連結: https://zerojudge.tw/ShowProblem?problemid=d129
# 內容
Ugly Number 的定義為：該數之質因數必須為 2, 3 或 5
當然了，依照慣例，1 也算是 Ugly Number。
在此列舉一串數列：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15
這些就是前 11 個 Ugly Numbers。
請寫一個程式求出第 1500 個 Ugly Number。
# 解題思路
因為數字地 1500 項有點大，窮舉起來有些許費時，所以，使用 set 將每項的 2、3、5 的倍數都加進來，因為 set 會自動排序，所以能很快速的求到答案。
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
int s = 1; | |
set<long long>ugly_N(&s,&s+1); | |
set<long long>::iterator p; | |
for(int i=0;i<1500;i++){ | |
p=ugly_N.begin(); | |
ugly_N.insert(*p * 2); | |
ugly_N.insert(*p * 3); | |
ugly_N.insert(*p * 5); | |
ugly_N.erase(p); | |
} | |
printf("The 1500'th ugly number is %d.",*p); | |
} |
