使用埃氏筛法

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdbool.h>

#define MAX 110000  // 第10000个质数约为104729，预留空间

int main() {

    int n;

    scanf("%d", &n);

    bool is_prime[MAX] = {false};

    int prime[10001];  // 存储找到的质数，只需10000个

    int count = 0;     // 已找到的质数个数

    // 埃氏筛法

    for (int i = 2; i < MAX && count < n; i++) {

        if (!is_prime[i]) {          // i是质数

            prime[++count] = i;      // 记录第count个质数（从1开始计数）

            // 标记i的倍数

            if ((long long)i * i < MAX) {

                for (int j = i * i; j < MAX; j += i) {

                    is_prime[j] = true;

                }

            }

        }

    }

    printf("%d\n", prime[n]);

    return 0;

}