gap - 题目列表

题目描述

给定正整数 $N$ （ $N \leqslant 10^6$ ）。把不小于 2 的素数从小到大记为 $p_1=2,p_2=3,p_3=5,\dots$ ，约定素数间距 $g_i=p_{i+1}-p_i$ ：若 $p_i<N<p_{i+1}$ 则输出 $g_i$ ，特别地，若 $N$ 本身是素数则输出 $0$ 。输入一行一个正整数 $N$ ，输出一行一个整数表示答案。样例输入 10，样例输出 4（ $10$ 夹在素数 $7$ 与 $11$ 之间，间隔 $11-7=4$ ）。

思路

答案只由 $N$ 落在哪一对相邻素数之间决定：同一段 gap 里的合数共享宽度 $p_{i+1}-p_i$ ，而 $N$ 本身是素数时为 $0$ 。于是用线性筛（欧拉筛）升序筛出素数，再扫一遍相邻素对，把区间内每个合数的答案统一登记，询问时直接查表。注意 $N=10^6$ 右侧的第一个素数是 $1000003$ ，筛表要外扩一点才能给它登记答案。

参考代码

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
41
42
43
44
45
46
47
48
49#!/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-10-02 19:08
# update_at: 2026-10-02 19:22

import sys

LIMIT = 1_000_000  # 题面 N 的上界
SIEVE = LIMIT + 100  # 筛表外扩：N=10^6 时需要知道它右侧第一个素数 1000003


def prime_gaps(limit: int) -> list[int]:
    """返回 gap[v]：合数 v 所处素数间隔的宽度（v 为素数时记 0）。

    欧拉筛按从小到大顺序生成素数列表 p，p[i] 与 p[i+1] 之间的合数 v
    满足 p[i] < v < p[i+1]，其间隔宽度就是 p[i+1] - p[i]。
    """
    gap = [0] * (limit + 1)
    composite = bytearray(limit + 1)
    primes: list[int] = []
    for v in range(2, limit + 1):
        if not composite[v]:  # v 未被更小的素数划掉，v 是素数
            primes.append(v)
        # 用 v 和已筛出的每个素数 p 去划掉 p*v，p 取到 v 的最小素因子为止
        for p in primes:
            if v * p > limit:
                break
            composite[v * p] = 1
            if v % p == 0:  # p 是 v 的最小素因子，再大的素数交给后续轮次
                break

    # 前一个素数 prev 与当前素数 p 之间的每个合数都登记间隔 p - prev
    prev = 2
    for p in primes[1:]:
        for v in range(prev + 1, p):
            gap[v] = p - prev
        prev = p
    return gap


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    print(prime_gaps(SIEVE)[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
44
45
46
47
48
49
50
51
52
53
54
55/**
 * 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-04 22:17
 * update_at: 2026-10-04 22:17
 */
#include <cstdio>

const int LIMIT = 1000000;      // 题面中 N 的上界
const int SIEVE = LIMIT + 100;  // 筛表外扩，保证 N=10^6 时能取到它右侧的素数 1000003

int composite[SIEVE + 1];  // composite[v] = 1 表示 v 是合数
int primes[SIEVE + 1];     // 欧拉筛按从小到大存放素数
int gap[SIEVE + 1];        // gap[v]：合数 v 所处素数间隔的宽度；v 本身是素数时保持 0
int prime_cnt;             // 筛出的素数个数

// 欧拉筛：每个合数只被它的最小素因子划掉一次，整体 O(SIEVE)。
void euler_sieve() {
    for (int v = 2; v <= SIEVE; v++) {
        if (composite[v] == 0) {
            primes[++prime_cnt] = v;
        }
        for (int i = 1; i <= prime_cnt; i++) {
            if (primes[i] > SIEVE / v) {
                break;  // 再乘下去会超出筛表上界，用除法判断避免溢出
            }
            composite[v * primes[i]] = 1;
            if (v % primes[i] == 0) {
                break;  // primes[i] 已是 v 的最小素因子，更大的素因子留给后面的轮次
            }
        }
    }
}

// 把每对相邻素数之间的合数统一登记为这段间隔的宽度。
void fill_gap() {
    for (int i = 2; i <= prime_cnt; i++) {
        int left = primes[i - 1];
        int right = primes[i];
        for (int v = left + 1; v < right; v++) {
            gap[v] = right - left;
        }
    }
}

int main() {
    euler_sieve();
    fill_gap();

    long long n;
    scanf("%lld", &n);
    printf("%d\n", gap[n]);
    return 0;
}

⚠ 题面文件的说明（PDF 文本提取失败）

本题上游只有 content.pdf（无 content.md）。用 extract_pdf.py 提取时 得到乱码（常用汉字 0 个，如 ีଢ૭ඍ）—— 该 PDF 的内嵌字体缺少 ToUnicode CMap，无法还原字符（T66 的更严重形态）。

⇒ 本目录保留原始 problem.pdf 作为题面依据； index.md 的题意来自对 PDF 的人工阅读与推导。

★ 若后续取得可读题面（或带 CMap 的 PDF），可重跑提取替换 problem.pdf。