题目：
我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。习惯上把1当做第一个丑数
解法一：
判断一个数是否是丑数：
bool isUglyNumber(int number) {
while (number % 2 == 0) {
number /= 2;
}
while (number % 3 == 0) {
number /= 3;
}
while (number % 5 == 0) {
number /= 5;
}
return number == 1 ? true : false;
}
那么要求第n个丑数，依次迭代即可。
解法二：
思考丑数是怎么形成的——都是前面已有丑数乘以2、3或5生成的。假设已有丑数已按增序排列，那么下一个丑数一定是已有丑数分别乘以2、3、5得到的数中大于当前最大丑数中的最小的一个。优化：在乘以2得到的丑数当中有小于当前最大丑数的，也有大于当前最大丑数的，而且一定是某个点前面的小于，后面的大于，我们只需要那个点即可。对于乘以3得到的丑数、乘以5得到的丑数同理。
int min(const int a, const int b, const int c) {
int min = a < b ? a : b;
return min < c : min :c;
}
int getUglyNumber(int index) {
vector<int> uglyNumbers;
uglyNumbers.push_back(1);
int cnt = 1;
int p2 = 0;
int p3 = 0;
int p5 = 0;
while (cnt < index) {
uglyNumbers.push_back(min(uglyNumbers[p2]*2, uglyNumbers[p3]*3, uglyNumbers[p5]*5));
++cnt;
while (uglyNumbers[p2]*2 <= uglyNumbers[cnt-1]) ++p2;
while (uglyNumbers[p3]*3 <= uglyNumbers[cnt-1]) ++p3;
while (uglyNumbers[p5]*5 <= uglyNumbers[cnt-1]) ++p5;
}
return uglyNumbers[cnt-1];
}
