区间内的真素数

题目描述

如果一个正整数 P 是素数，且它的反序数（十进制数字倒过来组成的正整数，前导 0 自动消失，如 13 的反序数是 31）也是素数，就称 P 为真素数。输入两个数 M 和 N（空格间隔， $1 \leqslant M \leqslant N \leqslant 100000$ ），按从小到大输出 M 和 N 之间（包括端点）的所有真素数，逗号间隔、无空格；若没有真素数则输出 No。样例：输入 10 35，输出 11,13,17,31。

思路

反序数可能落在区间之外（如 17 的反序数是 71），所以用埃氏筛把整个值域 $[0, 10^5]$ 一次建成素数表，之后判素都是 $O(1)$ 查表。枚举区间内每个数，查自身与反序数是否都为素数，边枚举边用逗号拼接输出，一个都没找到时输出 No。

参考代码

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#!/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 09:16
# update_at: 2026-09-30 09:16

import sys
from math import isqrt

LIMIT = 100000  # N 的上界：任意 x ≤ LIMIT 的反序数也 ≤ LIMIT，一张筛表覆盖全部判素需求


def reversed_number(n: int) -> int:
    """反序数：把 n 的十进制数字倒过来组成的数，前导 0 自动消失（100000 → 1）。"""
    return int(str(n)[::-1])


# 埃氏筛：IS_PRIME[i] = 1 当且仅当 i 是素数，覆盖 [0, LIMIT]
IS_PRIME = bytearray([1]) * (LIMIT + 1)
IS_PRIME[0] = IS_PRIME[1] = 0
for i in range(2, isqrt(LIMIT) + 1):
    if IS_PRIME[i]:
        IS_PRIME[i * i :: i] = bytearray(len(range(i * i, LIMIT + 1, i)))  # 从 i² 起、步长 i 的位置全是合数


def truth_primes_in(m: int, n: int) -> list[str]:
    """[m, n] 内的真素数：自身与反序数都在筛表中；反序数可能落在区间外，查的是同一张全局筛表。"""
    return [str(i) for i in range(m, n + 1) if IS_PRIME[i] and IS_PRIME[reversed_number(i)]]


def solve() -> None:
    m, n = map(int, sys.stdin.buffer.read().split())
    ans = truth_primes_in(m, n)
    print(','.join(ans) if ans else 'No')


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/**
 * 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:15
 * update_at: 2026-10-05 23:15
 */
#include <cstdio>

typedef long long ll;

const int MAXV = 100000; // 值域上限，自身和反序数都不会超过它

// is_composite[i] = true 表示 i 是合数；反序数可能落在区间外，所以筛表必须覆盖全值域
bool is_composite[MAXV + 5];

// 埃氏筛：一次性建出 [0, MAXV] 的素数表，之后判素 O(1) 查表
void sieve() {
    is_composite[0] = is_composite[1] = true;
    for (int i = 2; i * i <= MAXV; ++i)
        if (!is_composite[i])
            for (int j = i * i; j <= MAXV; j += i)
                is_composite[j] = true;
}

int main() {
    sieve();

    int m, n;
    scanf("%d %d", &m, &n);

    bool first = true;      // 控制逗号只在数字之间输出
    bool found = false;     // 区间内是否找到真素数
    for (int i = m; i <= n; ++i) {
        if (is_composite[i]) continue;

        // 求 i 的反序数：逐位取出再拼回去，前导 0 自动消失
        int rev = 0;
        for (int t = i; t > 0; t /= 10)
            rev = rev * 10 + t % 10;

        if (!is_composite[rev]) {
            if (!first) printf(",");
            printf("%d", i);
            first = false;
            found = true;
        }
    }

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

目录

题目描述

思路

参考代码