( humble 不是谦虚的、卑微的意思么。。。为什么大家都说
Humble Numbers 是丑数?)
题意：
输出第n个丑数。 Humble Number就是质因子只有2、3、5、7的数。
思路：
由于这个数总是2、3、5、7的倍数，所以每个数都可以分解成有限个2 3 5 7 的乘积，
dp方程为 dp[i]=f[i]=min(min(dp[p2]*2,dp[p3]*3),min(dp[p5]*5,f[p7]*7))
找到比f[i-1]大且最小的数。
由于新找到的数可能可以由多个dp[pi]*i(i=2、3、5、7）得到。为了避免找到的数出现重复，
要用四个if语句而不是if。。。else if。。。else if。。。else。。
输出的时候由于
11、12、13是以1、2、3结尾但是英语中仍然是th结尾的，所以要单独考虑后缀。
而20以后所有以1、2、3结尾的都同1、2、3的后缀一样为st、nd、rd。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[5900];
void init()
{
int p2,p3,p5,p7;
dp[1]=1;
p2=p3=p5=p7=1;
for(int i=2;i<=5842;i++)
{
dp[i]=min(min(2*dp[p2],3*dp[p3]),min(5*dp[p5],7*dp[p7]));
if(dp[i]==dp[p2]*2) p2++;
if(dp[i]==dp[p3]*3) p3++;
if(dp[i]==dp[p5]*5) p5++;
if(dp[i]==dp[p7]*7) p7++;
}
}
int main()
{
init();
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
if(n%100>=10 && n%100<=20)
printf("The %dth humble number is %d.\n",n,dp[n]);
else
{
if(n%10==1)
printf("The %dst humble number is %d.\n",n,dp[n]);
else if(n%10==2)
printf("The %dnd humble number is %d.\n",n,dp[n]);
else if(n%10==3)
printf("The %drd humble number is %d.\n",n,dp[n]);
else
printf("The %dth humble number is %d.\n",n,dp[n]);
}
}
return 0;
}