ACM 136 Ugly Numbers

一開始很天真的以為只要可以被2, 3, 5整除就ok！
實際上是因數只能有2, 3, 5。
最蠢的作法就是從1開始，一直往上找，
能被2, 3, 5整除就記錄下來，如此可以找到第1500筆。
但這實在太慢了！
真的這樣做，會超過3秒TE。
所以就先算出答案，
再直接輸出答案即可。

上傳答案用

#include <stdio.h>
 
int main(void)
{
    puts("The 1500'th ugly number is 859963392.");
    return 0;
}

超級慢會TE的code

/* ACM 136
 * mythnc
 * 2011/10/25 08:44:33   
 * run time: TE
 */
#include <stdio.h>
 
#define NTH 1500
 
int main(void)
{
    int count, n, i;
 
    count = 0;
    n = 0;
    while (count < NTH) {
        n++;
        i = n;
        while (1) {
            if (i == 1) {
                count++;
                break;
            }
            if (i % 2 == 0)
                i /= 2;
            else if (i % 3 == 0)
                i /= 3;
            else if (i % 5 == 0)
                i /= 5;
            else
                break;
        }
    }
    printf("The %d'th ugly number is %d.\n", NTH, n);
    return 0;
}