素数对

题目描述

两个相差为 2 的素数称为素数对，如 5 和 7、17 和 19。给定正整数 $n$ （ $1 \leqslant n \leqslant 10000$ ），要求找出所有两个数均不大于 $n$ 的素数对，每对输出一行，中间用单个空格隔开。若没有找到任何素数对，输出 empty。

思路

先用埃氏筛预处理出 $[0, n]$ 内的素数标记表；再枚举奇数 $p$ ，若 $p$ 与 $p + 2$ 均为素数则输出这一对。因为除 2 外素数都是奇数，而 $(2, 4)$ 不合法，所以从 $p = 3$ 开始按步长 2 枚举即可；一对手都没有时输出 empty。

参考代码

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
50
51#!/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-09-30 08:46
# update_at: 2026-10-04 13:26

import sys
from collections.abc import Iterator


def sieve_primes(limit: int) -> bytearray:
    """使用埃氏筛生成 [0, limit] 的素数标记表：1 表示素数，0 表示合数。"""
    is_prime = bytearray([1]) * (limit + 1)
    if limit >= 0:
        is_prime[0] = 0
    if limit >= 1:
        is_prime[1] = 0

    upper = int(limit**0.5)
    for p in range(2, upper + 1):
        if is_prime[p]:
            is_prime[p * p : limit + 1 : p] = b"\x00" * len(range(p * p, limit + 1, p))
    return is_prime


def find_twin_primes(n: int) -> Iterator[tuple[int, int]]:
    """依次产出所有两数均不超过 n 的素数对 (p, p + 2)。"""
    if n < 5:
        return
    is_prime = sieve_primes(n)
    for p in range(3, n - 1, 2):
        if is_prime[p] and is_prime[p + 2]:
            yield (p, p + 2)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:  # 空输入直接返回
        return

    pairs = list(find_twin_primes(n))
    if not pairs:
        print("empty")
    else:
        print("\n".join(f"{p} {p + 2}" for p, _ in pairs))


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/**
 * 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 23:02
 * update_at: 2026-10-05 23:02
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 10005;

bool is_prime[MAXN]; // is_prime[i] 表示 i 是否为素数（埃氏筛结果）

int main() {
    ll n;
    scanf("%lld", &n);

    // 埃氏筛：把 0、1 标记为非素数，其余先假设是素数
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) is_prime[i] = true;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            for (int j = i * i; j <= n; j += i) // 从 i*i 开始筛 i 的倍数
                is_prime[j] = false;

    bool found = false; // 是否找到过素数对
    // 除 2 以外的素数都是奇数，且 (2,4) 不合法，只需枚举奇数 p
    for (ll p = 3; p + 2 <= n; p += 2) {
        if (is_prime[p] && is_prime[p + 2]) {
            printf("%lld %lld\n", p, p + 2);
            found = true;
        }
    }

    if (!found) printf("empty\n");
    return 0;
}

目录

题目描述

思路

参考代码