1136. Humble Numbers

import java.io.*;
import java.util.*;

public class Main {

    /**
     * http://acm.tju.edu.cn/toj/showp1136.html
     * @author hunglee
     */
    public static void main(String[] args) throws IOException {
        
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        
        int n, nhumbles = 0;
        int[] humble = new int[5842];
        final long MAX = 2000000000;
        
        
        long res = 1;
        for (int i = 0; ; ++i) {
            if (res > MAX) break;
            for (int j = 0; ; ++j) {
                if (res > MAX) {
                    res /= (long) Math.pow(3, j);
                    break;
                }
                for (int h = 0; ; ++h) {
                    if (res > MAX) {
                        res /= (long) Math.pow(5, h);
                        break;
                    }
                    for (int k = 0; ; ++k) {
                        if (res > MAX) {
                            res /= (long) Math.pow(7, k);
                            break;
                        }
                        humble[nhumbles++] = (int) res;
                        res *= 7;
                    }
                    res *= 5;
                }
                res *= 3;
            }
            res = res << 1;
        }
        Arrays.sort(humble);
        
        do {
            in.nextToken();
            n = (int) in.nval;
            if (n == 0) break;

           if (n % 10 == 1 && n%100 != 11)
               System.out.println("The " + n + "st humble number is " + 
                       humble[n - 1] + ".");
           else if (n % 10 == 2 && n % 100 != 12)
               System.out.println("The " + n + "nd humble number is " +
                       humble[n - 1] + ".");
           else if (n % 10 == 3 && n % 100 != 13)
               System.out.println("The " + n + "rd humble number is " + 
                       humble[n - 1] + ".");
           else 
               System.out.println("The " + n + "th humble number is " + 
                       humble[n-1] + ".");
        } while (true);
    }

}