hdu1058 Humble Numbers

http://acm.hdu.edu.cn/showproblem.php?pid=1058

DP

#include <stdio.h>
#define N 5848

int h[N];

int a[4];
int p[4] = {1, 1, 1, 1};

int min()
{
    int i, flag = 0;
    for(i=1; i<4; i++)
    {
        if(a[i] < a[flag])
        {
            flag = i;
        }
    }
    for(i=0; i<4; i++)
    {
        if(a[i] == a[flag])
        {
            p[i] ++;
        }
    }
    return a[flag];
}

void init()
{
    int hash[4] = {2, 3, 5, 7};
    int i, j;
    h[1] = 1;
    for(i=2; i<N; i++)
    {
        for(j=0; j<4; j++)
        {
            a[j] = h[p[j]] * hash[j];
        }
        h[i] = min();
        //printf("%d ", h[i]);
    }
}

int main()
{
    int i;
    init();
    while(scanf("%d", &i), i)
    {
        printf("The %d", i);
        if((10<i%100 && i%100<20) || i%10>3 || i%10==0)
        {
            printf("th");
        }
        else
        {
            if(i%10==1)
            {
                printf("st");
            }
            else
            {
                if(i%10==2)
                {
                    printf("nd");
                }
                else
                {
                    printf("rd");
                }
            }
        }
        printf(" humble number is %d.\n", h[i]);
    }
    return 0;
}