POJ 2247 humble number (DP)

这题第一感觉就是筛数法，可能是受前几天刚做的那题影响了。。。其实思路也没有太大问题，小数据的话还是可以的（虽然没优化过 = =）结果没想到题目的数据太大，堆溢出了 = =！所以就只好换一种思路吧。。。。
这题和ugly number 那题想法是可以完全一样的，还算蛮清晰，就是输出那里比较变态，估计坑了不少人。。。
网上看到有链表的做法，感觉上比这个要繁琐了，其实就是经典动规题。
核心思路就是用2,3,5,7和humble list中的数相乘，得出的数依然在list之内。
假设humble number集合开始只有{1}
2,3,5,7分别从集合中由小到大取数相乘后，
即2 * 1,3 * 1,5 * 1,7 * 1，min = 2，入队列{1,2}。
然后比较2 * 2,3 * 1，5 * 1,7 * 1，min = 3，入队列{1,2,3}。
.....


#include<cstdio>
int humble[6000];
int main(){
int t2,t3,t5,t7,p2,p3,p5,p7,i,min;
p2 = p3 = p5 = p7 = 1;
humble[1] = 1;
for(i = 1;i < 5843;i ++){
t2 = humble[p2] * 2;
t3 = humble[p3] * 3;
t5 = humble[p5] * 5;
t7 = humble[p7] * 7;
min = t2 < t3 ? t2 : t3;
min = min < t5 ? min : t5;
min = min < t7 ? min : t7;
humble[i+1] = min;
if(min == t2)p2 ++;
if(min == t3)p3 ++;
if(min == t5)p5 ++;
if(min == t7)p7 ++;
}
while(scanf("%d",&i) && i){
if(i % 10 == 1){
if(i % 100 == 11)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %dst humble number is %d.\n",i,humble[i]);
continue;
}
if(i % 10 == 2){
if(i % 100 == 12)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %dnd humble number is %d.\n",i,humble[i]);
continue;
}
if(i % 10 == 3){
if(i % 100 == 13)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %drd humble number is %d.\n",i,humble[i]);
continue;
}
else printf("The %dth humble number is %d.\n",i,humble[i]);
}
return 0;
}





筛法部分代码（未优化版）
-------------------------------
#include<cstdio>
#include<memory.h>
const int MAX = 1000000
int *num1 = new int[MAX];    //heap overflow...
int *num2 = new int[MAX];
int prime_list[10000];
int humble[5000];
int main()
{
int i,j,k,n;
for(i = 2;i < 1000;i ++)
if(num1[i] == 0)
for(j = i * i;j < MAX;j += i)num1[j] = 1;
for(i = 2,k = 0;i < MAX;i ++)
if(num1[i] == 0){prime_list[k] = i;k ++;}      //prime number list
delete []num1;
for(i = 4;i < k;i ++)
for(j = prime_list[i];j < MAX;j += prime_list[i])
num2[j] = 1;
for(i = 1,k = 1;i < MAX;i ++)
if(num2[i] == 0){humble[k] = i; k ++;}         //humble number list
while(scanf("%d",&n) && n)
printf("The %dst humble number is %d.\n",n,humble[n]);
delete []num2;
return 0;
}