usaco-1.5.2 回文质数

题目描述

因为 151 既是一个质数又是一个回文数（从左到右和从右到左读一样），所以 151 是回文质数。写一个程序找出范围 $[a, b]$ （ $5 \le a < b \le 100{,}000{,}000$ ）间的所有回文质数。

输入第 1 行是两个整数 $a$ 和 $b$ 。输出区间内所有回文质数，按升序一行一个。

样例输入 5 500，样例输出为 5 7 11 101 131 151 181 191 313 353 373 383，每行一个数。

思路

区间很大但回文数极少，所以不逐个数判断，而是按"前半段 + 中间位 + 反转前半段"直接构造 3、5、7 位回文数再试除判素。关键性质：偶数位回文数的奇偶位交错和为 0，必是 11 的倍数，因此除 11 外所有偶数位回文数都不是质数，只需再特判一位数和 11。

参考代码

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
52
53
54
55
56
57
58
59
60#!/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-01 03:06
# update_at: 2026-10-01 03:06

import sys
from collections.abc import Iterator


def is_prime(n: int) -> bool:
    """判定整数 n 是否为素数。"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    return all(n % d != 0 for d in range(3, int(n**0.5) + 1, 2))


def generate_palindromes(limit: int) -> Iterator[int]:
    """生成不超过 limit 的所有可能回文质数候选。

    除 11 外，任意偶数长度回文数的奇偶位交错和为 0，必是 11 的倍数且大于 11，
    故只需生成 1 位、2 位(仅11)以及 3, 5, 7 位奇数长度回文。
    """
    # 1 位数: 5, 7
    yield from (d for d in range(1, 10) if d <= limit)

    # 2 位数: 仅 11 可能是质数
    if 11 <= limit:
        yield 11

    # 3, 5, 7, 9 位数：由前半部 root (10^(k-1) .. 10^k-1) 与中间数 mid 拼出
    for half_len in (1, 2, 3, 4):
        start = 10 ** (half_len - 1)
        end = 10**half_len
        for root in range(start, end):
            rev_root = str(root)[::-1]
            for mid in range(10):
                val = int(f"{root}{mid}{rev_root}")
                if val > limit:
                    return
                yield val


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a, b = next(data), next(data)

    # 限制 b 最大 10^8，故奇数位回文上限至 10^8，直接过滤 [a, b] 内的素数
    pals = [p for p in generate_palindromes(b) if p >= a and is_prime(p)]
    pals.sort()
    print("\n".join(map(str, pals)))


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * 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-06 09:41
 * update_at: 2026-10-06 09:41
 */
// main.cpp：在 [a,b] 内找回文质数。
// 关键性质：除 11 外，偶数位回文数的奇偶位交错和为 0，必是 11 的倍数，
// 所以 10^8 以内只需枚举 1 位、2 位(仅 11)和 3/5/7 位回文数，再试除判素。
#include <cstdio>
#include <cstdlib>

typedef long long ll;

ll a, b; // 题目给出的区间 [a,b]，b 最大 10^8

// 试除法判定 n 是否为质数
bool is_prime(ll n) {
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (ll i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}

// 把数字反转（比如 123 -> 321），用于拼回文数的后半段
ll reverse_num(ll x) {
    ll rev = 0;
    while (x > 0) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return rev;
}

// 判断 x 是不是回文数
bool is_pal(ll x) {
    return x == reverse_num(x);
}

int main() {
    scanf("%lld %lld", &a, &b);

    // 1 位数和 11 单独处理
    for (ll x = a; x <= b && x < 100; ++x)
        if (is_pal(x) && is_prime(x))
            printf("%lld\n", x);

    // 枚举前半段 root，拼出 root + rev(root) 的 4/6/8 位回文数？
    // 不行：偶数位回文数除 11 外都是 11 的倍数，不可能是质数。
    // 所以只拼 3/5/7 位：root + 中间位 mid + rev(root)
    for (ll half = 1; half <= 1000; half *= 10) { // half = 1,10,100，对应 3/5/7 位
        for (ll root = half; root < half * 10; ++root) {
            ll rev = reverse_num(root);
            for (ll mid = 0; mid <= 9; ++mid) {
                // 拼法：root 后接 mid，再接反转的 root，得奇数位回文数
                ll x = (root * 10 + mid) * half * 10 + rev;
                if (x > b)
                    break; // mid 增大只会更大，直接退出
                if (x >= a && is_prime(x))
                    printf("%lld\n", x);
            }
        }
    }

    return 0;
}

usaco-1.5.2 回文质数

目录

题目描述

思路

参考代码