题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1216
思路：色筛法
代码（1）：
#include<iostream>//--------1216 HDU 埃拉托色尼筛选法
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
using namespace std;
#define Max 40000
bool b[Max];
__int64 a[Max], c;
void fun()
{
__int64 i, j, count;
c = ;
memset(b, true, sizeof(b));
b[] = ;
for (i = ; i < Max; ++i)
{
if (b[i])
{
a[++c] = i;
count = i;
for (j = i+; j < Max; ++j)
{
if (b[j] == true)
count--;
if (count == )
{
b[j] = false;
count = i;
}
}
}
}
}
int main()
{
fun();
int n;
while (scanf("%d", &n) != EOF)
{
if (n == )
break;
else
printf("%d\n", a[n]);
}
return ;
}
基本类似的另外一种：
#include<iostream>
#include<stdio.h>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define Max 40000
__int64 ans[Max];
__int64 pop[];
void dfs()
{
__int64 i, j, count;
for (i = ; i < Max; i++)
{
ans[i] = i;
}
for (i = ; i < Max; i++)
{
if (ans[i] != )
{
count = i;
for (j = i + ; j < Max; j++)
{
if (ans[j] != )
count--;
if (count == )
{
ans[j] = ;
count = i;
}
}
} }
j = ;
for (i = ; i <= ; i++)
{
while (ans[j] == )
{
j += ;
}
if (ans[j] != )
{
pop[i] = ans[j];
j += ;
}
}
}
int main()
{
dfs();
int n;
while (scanf("%d", &n)&&n)
{
printf("%d\n", pop[n]);
}
return ;
}