Poj 2247 Humble Numbers(求只能被2，3，5, 7 整除的数)

一、题目大意

本题要求写出前5482个仅能被2，3，5, 7 整除的数。

二、题解

这道题从本质上和Poj 1338 Ugly Numbers(数学推导)是一样的原理，只需要在原来的基础上加上7的运算即可。还有一个不同之处在于输出上，这个题要求第n的英语表示。而英语中的表示呢，如果n的个位数是1，用nst表示个位数是2的用，nnd表示；个位数是3的，用nrd表示。但是n的最后两位是11、12、13的还是用nth表示，其他的也是用th表示。

三、java代码

    import java.util.Scanner;

    public class Main {

        public static String format(int n){

        	if(n % 10==1 && n% 100 !=11)

        		return n+"st";

        	if(n % 10==2 && n% 100 !=12)

        		return n+"nd";

        	if(n % 10==3 && n% 100 !=13)

        		return n+"rd";

        	return n+"th";

        }

        public static void main(String[] args) {

            Scanner sc=new Scanner(System.in);

            int n;

            int i2_mul;

            int i3_mul;

            int i5_mul;

            int i7_mul;

            long[] ugly=new long[5843];

            i2_mul = 1;

            i3_mul = 1;

            i5_mul = 1;

            i7_mul = 1;

            ugly[1]=1;

            for(  int i = 2; i <= 5842; i++ ){

                ugly[i] = Math.min(Math.min(ugly[i2_mul]*2,

                		Math.min(ugly[i3_mul]*3,ugly[i5_mul]*5)), ugly[i7_mul]*7);

                if(ugly[i] == ugly[i2_mul]*2 )

                    i2_mul++;

                if(ugly[i] == ugly[i3_mul]*3 )

                    i3_mul++;

                if(ugly[i] == ugly[i5_mul]*5)

                    i5_mul++;

                if(ugly[i] == ugly[i7_mul]*7)

                    i7_mul++;

            }

            while((n=sc.nextInt())!=0){

                System.out.println("The "+format(n)+" humble number is "+ugly[n]+".");

            }

        }

    }