区间内的真素数的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求找出闭区间 $[M, N]$ ~[M, N]~ 内的所有真素数，即自身与其十进制反序均为素数的正整数，按数值从小到大用逗号连接输出，区间内不存在这样的数时输出 No。核心解法是直接枚举区间内的每个整数，用算术循环求出它的十进制反序，再对这两个数各做一次试除法素性判定。

分析

核心观察

判断一个正整数 $P$ ~P~ 是否为真素数需要两次素性测试： $P$ ~P~ 是素数，且 $P$ ~P~ 的十进制反序 $R$ ~R~ 也是素数，两次判定必须同时成立。由于 $P \le 10^5$ ~P \le 10^5~， $R$ ~R~ 至多为 $99999$ ~99999~（ $100000$ ~100000~ 的反序是 $1$ ~1~），两个数的量级都在 $10^5$ ~10^5~ 以内，试除法在两种情况下代价相当，不需要为反序单独做特殊处理。

另一个关键点是反转必须按数值理解：末尾的 $0$ ~0~ 反转后成为前导零并被丢弃，例如 $100$ ~100~ 的反序是 $1$ ~1~，所以 $100$ ~100~ 不是真素数。

思路

最直接的做法就是枚举：对区间内的每个整数 $i$ ~i~，用算术循环求出它的反序 $R$ ~R~，再用试除法分别判断 $i$ ~i~ 与 $R$ ~R~ 是否为素数，两者都是就输出 $i$ ~i~。反序用数值运算而不是字符串反转，末尾的 $0$ ~0~ 会被自然丢弃，与题面「反序」的数值含义天然一致；若改用 to_string 加 reverse，还需要一次 stoi 或 int 转换才能得到同样的数值。

试除法的单次素性判定上界是 $O(\sqrt{n})$ ~O(\sqrt{n})~，于是枚举的复杂度上界为 $O((N - M + 1)\sqrt{N})$ ~O((N - M + 1)\sqrt{N})~，看起来最坏达到 $10^5 \times 316 \approx 3 \times 10^7$ ~10^5 \times 316 \approx 3 \times 10^7~ 次取模。实际上这个上界只在判定对象是素数时才会取到：试除在找到第一个因子时立即退出，偶数一次就能排除， $3$ ~3~ 的倍数两次就能排除，只有 $10^5$ ~10^5~ 以内的 $9592$ ~9592~ 个素数会走满 $\sqrt{n}$ ~\sqrt{n}~。因此真实运算量约为 $10^6$ ~10^6~ 量级，本机实测最坏测试点（ $M = 1$ ~M = 1~、 $N = 10^5$ ~N = 10^5~）耗时在 C++ 与 Python 下都远低于 $0.1$ ~0.1~ 秒。

如果想进一步加速，可以先把 $10^5$ ~10^5~ 以内的素数表用埃氏筛预处理出来，此后每次素性判定降为 $O(1)$ ~O(1)~ 查表；但本题的数据规模并不需要这一步，直接枚举的写法更短、也不引入筛法的边界（ $0$ ~0~ 与 $1$ ~1~ 必须手动置为非素数）。

枚举按 $i$ ~i~ 递增进行，输出天然有序，无需排序。无解时题面要求输出 No，用一个布尔标志记录是否已经输出过至少一个数即可：枚举结束后标志仍为假就输出 No，否则依次输出逗号与数字。

具体示例

以样例 $M = 10$ ~M = 10~、 $N = 35$ ~N = 35~ 为例，区间内的素数为 $11, 13, 17, 19, 23, 29, 31$ ~11, 13, 17, 19, 23, 29, 31~，逐个求反序并判定：

$P$ ~P~	反序 $R$ ~R~	$R$ ~R~ 是否为素数	是否输出
$11$ ~11~	$11$ ~11~	是	是
$13$ ~13~	$31$ ~31~	是	是
$17$ ~17~	$71$ ~71~	是	是
$19$ ~19~	$91 = 7 \times 13$ ~91 = 7 \times 13~	否	否
$23$ ~23~	$32$ ~32~	否	否
$29$ ~29~	$92$ ~92~	否	否
$31$ ~31~	$13$ ~13~	是	是

按递增顺序拼接得到 11,13,17,31，与样例输出一致。

算法步骤

读入 M 与 N。
从 i = M 到 i = N 依次枚举：令 x 等于 i、r 等于 $0$ ~0~，循环执行 r = r * 10 + x % 10 与 x //= 10，直到 x 为 $0$ ~0~，此时 r 就是 i 的反序。
用试除法判断 i 是否为素数：i 小于 $2$ ~2~ 时直接判否，否则先排除偶数，再从 $3$ ~3~ 开始以步长 $2$ ~2~ 试除到 $\sqrt{i}$ ~\sqrt{i}~。
若 i 是素数，用同样的方法判断 r 是否为素数；两者都是素数时把 i 追加到答案缓冲，并在追加前处理逗号分隔。
枚举结束后：答案缓冲为空则输出 No，否则输出拼接好的答案。
输出末尾补一个换行。

复杂度分析

时间：枚举 $N - M + 1$ ~N - M + 1~ 个数，每个数求反序需要 $O(\log_{10} N)$ ~O(\log_{10} N)~（ $N \le 10^5$ ~N \le 10^5~ 时至多 $6$ ~6~ 位数字），两次试除法素性判定的上界为 $O(\sqrt{N})$ ~O(\sqrt{N})~，故最坏情况为 $O((N - M + 1)\sqrt{N})$ ~O((N - M + 1)\sqrt{N})~。实际运算量远小于该上界，因为试除在命中小因子时立即退出。
空间：只需常数个辅助变量与答案缓冲，为 $O(N - M + 1)$ ~O(N - M + 1)~（缓冲为输出本身）。

实现注意事项

小于 $2$ ~2~ 的数不是素数：1 必须判否，否则 1 以及反序为 1 的数（如 10、100）会被误判为真素数。
反序按数值处理： $100$ ~100~ 的反序写作 001，其数值为 $1$ ~1~，故 $100$ ~100~ 不是真素数；算术反转天然丢弃末尾的 $0$ ~0~。
反序的值域不会超过原来的上界（ $1 \sim 10^5$ ~1 \sim 10^5~ 内最大的反序为 $99999$ ~99999~），不需要额外的越界判断。
先判 i 再判 r：合数占绝大多数，短路求值能让第二次素性判定只在必要时执行（Python 的 and 与 C++ 的 && 都短路）。
试除从 $3$ ~3~ 开始、步长为 $2$ ~2~，跳过偶数可省掉一半试除次数；i 为 $2$ ~2~ 时要单独返回真。
逗号只加在相邻两项之间，末尾不能有多余逗号：用一个标志判断当前项是不是第一项。
空答案的标志同时用作 No 的判定依据，No 只能在枚举全部结束后输出，不能在前缀暂时为空时提前输出。
题目保证 $M \le N$ ~M \le N~，输入的两个数不需要交换。
No 是完整的输出内容（首字母大写、不含其他字符），后面只跟一个换行。
输出用缓冲拼接后一次写出：C++ 用 std::string 累加再 fwrite，Python 用 join，比逐项输出更快。
Python 读入用 sys.stdin.buffer.read().split() 一次取完即可。

源代码

#include <cstdio>
#include <iostream>
#include <string>

namespace {

bool isPrime(int n) {
    if (n < 2) return false;       // 0 与 1 都不是素数
    if (n % 2 == 0) return n == 2; // 2 是唯一的偶素数
    for (long long d = 3; d * d <= n; d += 2) {
        if (n % d == 0) return false;
    }
    return true;
}

// 十进制反序：末尾的 0 在反转后自动消失（100 → 1）
int reverseDecimal(int n) {
    int r = 0;
    while (n > 0) {
        r = r * 10 + n % 10;
        n /= 10;
    }
    return r;
}

}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int m = 0, n = 0;
    if (!(std::cin >> m >> n)) return 0;

    std::string out;
    bool first = true;
    for (int i = m; i <= n; ++i) {
        if (!isPrime(i)) continue;            // 先判自身，短路掉大部分数
        const int r = reverseDecimal(i);
        if (!isPrime(r)) continue;
        if (!first) out += ',';
        out += std::to_string(i);
        first = false;
    }
    if (first) out += "No";
    out += '\n';
    std::fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

import sys


def is_prime(n):
    if n < 2:
        return False          # 0 与 1 都不是素数
    if n % 2 == 0:
        return n == 2         # 2 是唯一的偶素数
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True


def reverse_decimal(n):
    r = 0
    while n > 0:              # 末尾的 0 在反转后自动消失（100 → 1）
        r = r * 10 + n % 10
        n //= 10
    return r


def main():
    data = sys.stdin.buffer.read().split()
    if len(data) < 2:
        return
    m, n = int(data[0]), int(data[1])

    res = [str(v) for v in range(m, n + 1)
           if is_prime(v) and is_prime(reverse_decimal(v))]

    sys.stdout.write(",".join(res) if res else "No")
    sys.stdout.write("\n")


if __name__ == "__main__":
    main()

目前没有评论。