http://ac.jobdu.com/problem.php?pid=1040
两种方法：
#include <stdio.h> #include <cmath> #include <cstring> #define MAXN 2000000 static int primes[10001],nPrimes; static bool mark[MAXN]; void init0(){ memset(mark,true,sizeof(mark)); nPrimes=0; for (int i = 2; i < MAXN ; ++i) { if(!mark[i]) continue; primes[nPrimes++] = i; for (int j = i*i; j < MAXN; j+=i) { mark[j] = false; } } } bool judge(int n){ if(n<=1) return false; if(n==2) return true; if(n%2==0) return false; for (int i = 3; i <=sqrt(n) ; i+=2) { if(n%i == 0) return false; } return true; } void init1(int k){ nPrimes = 0; primes[nPrimes++] = 2; int i=3; while(nPrimes<k){ if(judge(i)) primes[nPrimes++] = i; i++; } } int main(){ // init0(); init1(10000); int k; while(scanf("%d",&k)!=EOF){ printf("%d\n",primes[k-1]); } }