1 /*
 2 Author:    Leo.W
 3 Descriptipn:尋找質因數僅為2、3、5、7其中若干的正整數    
 4 How to Do:    動態規劃，由2、3、5、7開始依次疊増；
 5   */
 6 #include <stdio.h>
 7 #include <string.h>
 8 int num[5900];
 9 inline int min(int a,int b){
10     if(a<b)    return a;
11     return b;
12 }
13 int main(){
14     //freopen("in.txt","r",stdin);
15     int i,t=1,p2=1,p3=1,p5=1,p7=1;//表示當前遞增依次為2、3、5、7
16     char ch[5][3]={"th","st","nd","rd"};
17     for(i=1;i<=5842;i++){
18         num[i]=t;
19         t=min(min(num[p2]*2,num[p3]*3),min(num[p5]*5,num[p7]*7));
20         if(t==num[p2]*2)
21             p2++;
22         if(t==num[p3]*3)
23             p3++;
24         if(t==num[p5]*5)
25             p5++;
26         if(t==num[p7]*7)
27             p7++;
28     }
29     while(scanf("%d",&t),t){
30         i=0;
31         if(t%100!=11&&t%10==1)
32             i=1;
33         if(t%100!=12&&t%10==2)
34             i=2;
35         if(t%100!=13&&t%10==3)
36             i=3;
37         printf("The %d%s humble number is %d.\n",t,ch[i],num[t]);
38 
39     }
40     return 0; 
41 }