素数回文数的个数

题目描述

求 $11$ 到 $n$ （包括 $n$ ）之间，既是素数又是回文数的整数有多少个。 $11<n<1000$ 。

思路

数据范围很小，直接枚举 $[11,n]$ 中的每个整数；先判断是否为回文数，再判断是否为素数，两个条件都满足则计数加一。把回文判定放在前面，多数数会被快速短路掉。

参考代码

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

import sys
from math import isqrt


def is_prime(x: int) -> bool:
    """试除法判素数：只要 2 ~ √x 里没有因子就是素数。"""
    return x >= 2 and all(x % d for d in range(2, isqrt(x) + 1))


def is_palindrome(x: int) -> bool:
    """回文判断：十进制表示正读反读一致。"""
    s = str(x)
    return s == s[::-1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    # 11 到 n 逐个检查：先滤回文（便宜），幸存者再滤素数（试除），
    # 两个条件都满足才计数；两位回文数都是 11 的倍数，幸存者极少
    print(sum(1 for i in range(11, n + 1) if is_palindrome(i) and is_prime(i)))


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/**
 * 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:12
 * update_at: 2026-10-05 23:11
 */
#include <iostream>
using namespace std;

typedef long long ll;

// 判断 x 是否为回文数：十进制表示左右对称
bool is_palindrome(ll x) {
    ll rev = 0, t = x;
    while (t > 0) {
        rev = rev * 10 + t % 10;
        t /= 10;
    }
    return rev == x;
}

// 判断 x 是否为素数：试除到 sqrt(x)
bool is_prime(ll x) {
    if (x < 2) return false;
    for (ll i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}

ll n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    ll ans = 0;
    // 先判回文（快且筛掉多数），再判素数
    for (ll i = 11; i <= n; ++i)
        if (is_palindrome(i) && is_prime(i)) ++ans;
    cout << ans << '\n';
    return 0;
}

素数回文数的个数

目录

题目描述

思路

参考代码