諾西筆試最后一道題，題意:
把只包含質因子2、3和5的數稱作丑數（Ugly Number），例如：2,3,4,5,6,8,9,10,12,15,等，習慣上我們把1當做是第一個丑數。
寫一個高效算法，返回第n個丑數。
最普通（也最耗時）的做法是從1開始遍歷，然后判斷這個數的因式分解中只包含2,3,5，滿足則找到了一個，一直找下去，直到第n個被找出！測試了一下，找第1500個丑數耗時40秒！
分析：假設數組ugly[N]中存放不斷產生的丑數，初始只有一個丑數ugly[0]=1，由此出發，下一個丑數由因子2,3,5競爭產生，得到ugly[0]*2, ugly[0]*3, ugly[0]*5， 顯然最小的那個數是新的丑數，所以第2個丑數為ugly[1]=2，開始新一輪的競爭，由于上一輪競爭中，因子2獲勝，這時因子2應該乘以ugly[1]才顯得公平，得到ugly[1]*2,ugly[0]*3,ugly[0]*5， 因子3獲勝，ugly[2]=3，同理，下次競爭時因子3應該乘以ugly[1]，即：ugly[1]*2, ugly[1]*3, ugly[0]*5, 因子5獲勝，得到ugly[3]=5，重復這個過程，直到第n個丑數產生。總之：每次競爭中有一個（也可能是兩個）因子勝出，下一次競爭中 勝出的因子就應該加大懲罰！
程序如下所示（只要把程序中的因子改一下就可以得到新的題目），耗時忽略不計：
運行結果：第1500個丑數：859963392， 第1691個丑數2 125 764 000，第1692個丑數就越界了。
int表示的最大整數是2,147,483,647，可由std::cout<<(std::numeric_limits<int>::max)()<<"\n";給出！
#include <iostream>
using namespace std;
int mymin(int a, int b, int c)
{
int temp = (a < b ? a : b);
return (temp < c ? temp : c);
}
int FindUgly(int n) //
{
int* ugly = new int[n];
ugly[0] = 1;
int index2 = 0;
int index3 = 0;
int index5 = 0;
int index = 1;
while (index < n)
{
int val = mymin(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5); //競爭產生下一個丑數
if (val == ugly[index2]*2) //將產生這個丑數的index*向后挪一位；
++index2;
if (val == ugly[index3]*3) //這里不能用elseif，因為可能有兩個最小值，這時都要挪動；
++index3;
if (val == ugly[index5]*5)
++index5;
ugly[index++] = val;
}
/**//*/
for (int i = 0; i < n; ++i)
cout << ugly[i] << endl;
//*/
int result = ugly[n-1];
delete[] ugly;
return result;
}
int main()
{
int num=1;
printf("input the number: \n");
scanf("%d", &num);
printf("%d \n",FindUgly(num));
return 0;
}