题干：

After the 1997/1998 Southwestern European Regional Contest (which was held in Ulm) a large contest party took place. The organization team invented a special mode of choosing those participants that were to assist with washing the dirty dishes. The contestants would line up in a queue, one behind the other. Each contestant got a number starting with 2 for the first one, 3 for the second one, 4 for the third one, and so on, consecutively. 
The first contestant in the queue was asked for his number (which was 2). He was freed from the washing up and could party on, but every second contestant behind him had to go to the kitchen (those with numbers 4, 6, 8, etc). Then the next contestant in the remaining queue had to tell his number. He answered 3 and was freed from assisting, but every third contestant behind him was to help (those with numbers 9, 15, 21, etc). The next in the remaining queue had number 5 and was free, but every fifth contestant behind him was selected (those with numbers 19, 35, 49, etc). The next had number 7 and was free, but every seventh behind him had to assist, and so on. 

Let us call the number of a contestant who does not need to assist with washing up a lucky number. Continuing the selection scheme, the lucky numbers are the ordered sequence 2, 3, 5, 7, 11, 13, 17, etc. Find out the lucky numbers to be prepared for the next contest party. 

Input

The input contains several test cases. Each test case consists of an integer n. You may assume that 1 <= n <= 3000. A zero follows the input for the last test case. 

Output

For each test case specified by n output on a single line the n-th lucky number. 

Sample Input

1
2
10
20
0

Sample Output

2
3
29
83

解题报告：

   这题刚开始就想错了，简单的想成了素数问题，所以上来就是个线性筛，结果wa了。。。后来一想发现并不是素数问题，因为在这种模式下有的素数是要被筛掉的。主要是因为这个题意：是数到第k个还健在的数字，并且筛掉这个数字，这就导致了，筛掉的数字不全是素数，也有一部分是合数，因为这里找到的i并不是数学上的约数的意义，换句话来讲，此时的i不是+i了，而有可能是+(i+1)，或是+(i+3)，+(i+2)等等、、、

   ps ：  这个打表的时间复杂度好像不是很好解释？暂时弄不明白、、、

AC代码：

//打表、、
#include<bits/stdc++.h>

using namespace std;

bool prime[40004];
int lucky[3005];
int n;
int main() 
{
	memset(prime,1,sizeof prime);
	for(int i = 1; i<=3000; i++) {
		for(int j = 2; j<=40000; j++) {
			if(prime[j]) {
				lucky[i] = j;
				prime[j]=0;
				int sum = 0;
				for(int k = j+1; k<=40000; k++) {
					if(prime[k]) {
						sum++;
						if(sum % j == 0) prime[k] = 0;
					}
				}
				break;
			}
		}
	}
	while(scanf("%d",&n)) {
		if(n == 0 ) break;

		printf("%d\n",lucky[n]);
	}
	
	return 0 ;
}