PKU 2247-Humble Numbers

2247 -- Humble Numbers

問題概要

素因数として，2，3，5，7しか含まない数をhumble数という．
n番目のhumble数を求めよ．
ただし，出力時の数詞は"nd","st","rd","th"を正しく使いわけろ．

解法

全探索．
数詞の部分に気を付ける

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner cin;
	String prefix(int x){
		x%=100;
		if(x==1)return "st";
		if(x==2)return "nd";
		if(x==3)return "rd";
		if(x<=20)return "th";
		if(x%10==1)return "st";
		if(x%10==2)return "nd";
		if(x%10==3)return "rd";
		return "th";
	}
	void run(){
		cin=new Scanner(System.in);
		List<Integer> res=new ArrayList<Integer>();
		long MAX=2000000000;
		for(long t=1;t<=MAX;t*=7){
			for(long q=1;q*t<=MAX;q*=5){
				for(long r=1;r*t*q<=MAX;r*=3){
					for(long s=1;q*t*r*s<=MAX;s*=2){
						res.add((int) (q*t*r*s));
					}
				}
			}
		}
		Collections.sort(res);
		int n;
		while((n=cin.nextInt())>0){
			printf("The %d%s humble number is %d.\n",n,prefix(n),res.get(n-1));
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}