POJ 2247 && HDU 1058 Humble Numbers

 

定义一种 humble 数，使得其中的元素的素数因子只能是 2 / 3 / 5 / 7
要求这个集合的第 n 个数是多少 

const int N=6e3+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];

/*int prime[N],num;
bool vis[N];
void init()
{
    for(i=2;i<N;i++){
        if(!vis[i]){
            prime[++num]=i;
            for(j=2;i*j<N;j++){
                vis[i*j]=1;
            }
        }
    }
}*/
void init()
{
    int p[10];
    p[2]=p[3]=p[5]=p[7]=1;
    a[1]=1;
    for(i=2;i<N;i++){
        a[i]=min( min(a[ p[2] ]*2,a[ p[3] ]*3) , min(a[ p[5] ]*5,a[ p[7] ]*7) );
        if(a[i]==a[ p[2] ]*2) p[2]++;
        if(a[i]==a[ p[3] ]*3) p[3]++;
        if(a[i]==a[ p[5] ]*5) p[5]++;
        if(a[i]==a[ p[7] ]*7) p[7]++;
    }
}
int main()
{
    //IOS;
    init();
    while(sd(n)!=EOF){
        if(n==0) break;
        if(n%100>10 && n%100<20)
            printf("The %dth humble number is %d.\n",n,a[n]);
        else if(n%10==1)
            printf("The %dst humble number is %d.\n",n,a[n]);
        else if(n%10==2)
            printf("The %dnd humble number is %d.\n",n,a[n]);
        else if(n%10==3)
            printf("The %drd humble number is %d.\n",n,a[n]);
        else printf("The %dth humble number is %d.\n",n,a[n]);
    }
    // PAUSE;
    return 0;
}