アルゴリズムノート練習問題解合集
タイトルリンク

タイトル

タイトルはOutput the k-th prime number.
k≦10000を入力
出力The k-th prime number.
サンプル入力

10
50

サンプル出力

29
229

構想

素数表をエルスふるいで打つ.

コード#コード#

#include 

//  
// [2,105000)   10024  ，  
#define MAX 105000

int table[MAX]; 
int isPrime[MAX];

int findPrime(void) {
	int i, j, cnt = 0;
	for (i = 2; i < MAX; ++i)
		isPrime[i] = 1;
	for (i = 2; i < MAX; ++i) {
		if (isPrime[i]) {
			table[cnt++] = i;
			for (j = i; j < MAX; j += i)
				isPrime[j] = 0;
		} 
	}
	return cnt;
} 

int main() {
	int n;
	int cnt = findPrime();
	while (scanf("%d", &n) != EOF)
		printf("%d
", table[n-1]);	//   n-1 
	return 0;
}