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。

Input

No input

Output

The 1500'th ugly number is <number>.

Attention: Your program must be smart enough to solve this problem in 30 seconds. If your program is not so efficient, it may take much time to run. Please be patient.

參考解答：這 題要列出的數字，其因數只能有2, 3, 或 5，所以，數字一定是 2^x * 3^y * 5^z的組合，參考他的解答，我使用一個 minUgly(2*x, 3*y, 5*z, &idx)的方式，注意這裡的x,y,z必須也是Ugly number，所以就必須有個index將uglyNum陣列中的數字一個個叫出來。 &idx是告訴你三個中，哪一個最小，這時才能將x,y,或z換大一點的Ugly number。
注意：不要用//，這個註解會產生compilation error。

    uglyNum[0] = 1;
    while (i<1500)
    {
        min = minUgly(2*fac[0], 3*fac[1], 5*fac[2], &idx);
        if (min>oldmin)
            i++;
        uglyNum[i] = min;
        maxFac[idx]++;
        fac[idx] = uglyNum[maxFac[idx]];
        oldmin = min;
    }