HDU - 1058

#include <iostream>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
int dp[5845];
void init()
{
    int a,b,c,d;
    a = b = c = d = 1;
    dp[1] = 1;
    for(int i=2 ;i<=5842;i++)
    {
        dp[i] = min(dp[a]*2, min(dp[b]*3, min(dp[c]*5,dp[d]*7)));
        if(dp[i] == dp[a]*2)
            a++;
        if(dp[i] == dp[b]*3)
            b++;
        if(dp[i] == dp[c]*5)
            c++;
        if(dp[i] == dp[d]*7)
            d++;
    }
}
int main()
{
    init();
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        cout<<"The "<<n;
        if(n%10 == 1&&n%100 != 11)
            cout<<"st ";
        else if(n%10 == 2&&n%100 != 12)
            cout<<"nd ";
        else if(n%10 == 3&&n%100 != 13)
            cout<<"rd ";
        else
            cout<<"th ";
        cout<<"humble number is "<<dp[n]<<"."<<endl;
    }
    return 0;
}