第n小质数

题目描述

给定一个不超过 $10000$ 的正整数 $n$ ，求第 $n$ 小的质数。例如质数升序为 $2,3,5,7,11,\dots$ ，第 $10$ 小的质数是 $29$ 。

输入输出：一行一个正整数 $n$ （ $n \leqslant 10000$ ）；输出一行，即第 $n$ 小的质数。

样例输入

text

样例输出

text

思路

由素数定理，第 $10000$ 个质数不超过 $105000$ ，先取 $L=105000$ 建埃拉托斯特尼筛：把每个质数从 $i^2$ 开始的倍数都标记为合数。筛完后按升序扫描，数到第 $n$ 个质数输出即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-06 10:30
# update_at: 2026-10-04 13:11

import sys
import math


def nth_prime(n: int) -> int:
    """返回第 n 小的质数（n >= 1）。用埃氏筛预筛到足够范围。"""
    # 第 10000 个质数是 104729，筛到 105000 足够；为保险按 n*12 向上取整。
    limit = max(2, int(n * (math.log(n) + math.log(math.log(n))) + 12) if n >= 6 else 12)
    sieve = bytearray(b"\x01") * (limit + 1)
    sieve[0:2] = b"\x00\x00"
    for i in range(2, int(limit ** 0.5) + 1):
        if sieve[i]:
            sieve[i * i : limit + 1 : i] = b"\x00" * ((limit - i * i) // i + 1)
    # 枚举时直接计数，第 n 个质数即为答案。
    count = 0
    for i, is_p in enumerate(sieve):
        if is_p:
            count += 1
            if count == n:
                return i
    return -1  # 理论上不会到达


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)  # 输入只有位置量 n；空输入按原样直接返回
    if n is None:
        return
    print(nth_prime(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:08
 * update_at: 2026-10-05 01:08
 */
#include <cstdio>

typedef long long ll;

const int MAXL = 105000; // 上界：第 10000 个质数是 104729，筛到 105000 足够

bool is_composite[MAXL + 1]; // is_composite[i] = true 表示 i 是合数

int main() {
    // 埃拉托斯特尼筛：枚举每个质数 i，从 i*i 开始标记它的倍数为合数
    for (ll i = 2; i * i <= MAXL; i++) {
        if (!is_composite[i]) {
            for (ll j = i * i; j <= MAXL; j += i) {
                is_composite[j] = true;
            }
        }
    }

    ll n; // 要求的质数序号
    scanf("%lld", &n);

    // 按升序扫描筛表，数到第 n 个质数即为答案
    ll count = 0;
    ll ans = 0;
    for (ll i = 2; i <= MAXL; i++) {
        if (!is_composite[i]) {
            count++;
            if (count == n) {
                ans = i;
                break;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码