革命烈士编号 题解

题目分析

本题要求找出区间 $[a, b]$ 中所有满足以下两个条件的整数：

1. 该数本身是素数；
2. 该数的各位数字之和也是素数。

满足这两个条件的数被称为“红色素数”。需要按从小到大的顺序输出所有红色素数，如果一个都没有则输出 NO。

例如：数字 11 是素数，各位数字之和 1+1=2 也是素数，因此 11 是红色素数。数字 19 是素数，但数位和 1+9=10 不是素数，所以 19 不是红色素数。

解题思路

整个问题可以拆分为两个步骤：

1. 素数的判断：写一个函数 isPrime(n)，判断一个数是否为素数。
2. 数位和的计算：写一个函数 getDigitSum(n)，计算一个数的各位数字之和。

然后，依次遍历 $[a, b]$ 中的每一个整数，先用 isPrime 判断该数本身是不是素数，如果是，再计算它的数位和，并判断数位和是不是素数。同时满足这两个条件的数就是红色素数，将其保存下来。

最后，根据保存的结果，如果没有符合条件的数就输出 NO，否则按顺序输出，数之间用空格分隔。

算法说明

1. 素数判断 isPrime(n)

判断一个数 $n$ 是否为素数，采用最常见的方法：

• 如果 $n<2$，不是素数；
• 如果 $n = 2$，是素数；
• 如果 $n$ 是偶数，不是素数（$2$ 除外）；
• 对于奇数，只需要检查 $3$ 到 $\sqrt{n}$ 之间的所有奇数，看是否有整除关系。如果都不能整除，那么 $n$ 就是素数。

这样做的时间复杂度为 $O(\sqrt{n})$。

在标准库 cmath 中可以使用 sqrt() 函数，但为了防止浮点数精度问题，一般采用 i * i <= n 来控制循环边界。

2. 数位和计算 getDigitSum(n)

将一个整数 $n$ 逐位拆分，把每一位的数字相加。可以通过不断取模 %10 和整除 /10 来实现，直到 $n$ 变为 $0$。

例如：$n = 123$，循环过程：

123 % 10 = 3, sum = 3, n = 12
12 % 10 = 2, sum = 5, n = 1
1 % 10 = 1, sum = 6, n = 0 (结束)

最终数位和为 $6$。时间复杂度是 $O(\log_{10} n)$，即 $n$ 的位数。

3. 主过程

• 读入区间起点 $a$ 和终点 $b$。
• 准备一个动态数组（如 vector）用来存放红色素数。
• 循环变量 i 从 $a$ 到 $b$：
  • 如果 isPrime(i) 为真，则计算 s = getDigitSum(i)；
  • 如果 isPrime(s) 也为真，就把 i 加入数组。
• 遍历完成后，如果数组为空输出 NO，否则依次输出数组元素，注意数字之间用空格分隔，且末尾不包含多余空格。

时间复杂度分析

假设区间长度为 $L = b - a + 1$，区间内最大值为 $b$。

• 素数判断 isPrime(x) 的时间复杂度为 $O(\sqrt{x})$，在本题中最坏为 $O(\sqrt{b})$。
• 数位和计算时间复杂度为 $O(\log_{10} x)$，相对很小。
• 整个过程需要对 $L$ 个数各进行一次素数判断，最坏情况下总时间复杂度约为 $O(L \cdot \sqrt{b})$。

由于题目没有给出 $a, b$ 的具体范围，但在“简单”难度下，$L$ 和 $b$ 通常不会太大，该算法可以直接通过。如果数据范围很大，则需要使用更高效的素数筛法预处理，但本题不需要。

参考代码

cpp
复制
1#include <iostream>
2#include <vector>
3#include <cmath>
4
5using namespace std;
6
7// 判断一个数是否为素数
8bool isPrime(int n) {
9    if (n < 2) return false;      // 0和1不是素数
10    if (n == 2) return true;      // 2是素数
11    if (n % 2 == 0) return false; // 排除偶数
12    
13    // 只需要检查到 sqrt(n)，步长为2跳过偶数
14    for (int i = 3; i * i <= n; i += 2) {
15        if (n % i == 0) return false;
16    }
17    return true;
18}
19
20// 计算一个数的各位数字之和
21int getDigitSum(int n) {
22    int sum = 0;
23    while (n > 0) {
24        sum += n % 10;  // 累加个位
25        n /= 10;        // 去掉个位
26    }
27    return sum;
28}
29
30int main() {
31    // 优化输入输出效率
32    ios_base::sync_with_stdio(false);
33    cin.tie(NULL);
34
35    int a, b;
36    if (!(cin >> a >> b)) return 0;
37
38    vector<int> results;
39
40    // 枚举区间 [a, b] 内的每一个整数
41    for (int i = a; i <= b; ++i) {
42        // 条件1：判断 i 本身是否为素数
43        if (isPrime(i)) {
44            // 条件2：计算数位和并判断是否为素数
45            int s = getDigitSum(i);
46            if (isPrime(s)) {
47                results.push_back(i);
48            }
49        }
50    }
51
52    // 输出结果
53    if (results.empty()) {
54        cout << "NO" << endl;
55    } else {
56        for (int i = 0; i < results.size(); ++i) {
57            if (i > 0) cout << " "; // 控制空格格式
58            cout << results[i];
59        }
60        cout << endl;
61    }
62
63    return 0;
64}

代码说明

1. isPrime 函数：

   • 首先判断 $n<2$ 直接返回 false；
   • $2$ 返回 true；
   • 偶数返回 false；
   • 从 $3$ 开始，以步长 $2$ 检查 $\sqrt{n}$ 以内的奇数，提高效率。

2. getDigitSum 函数：

   • 通过 while 循环不断取出个位并累加，直到数字为 $0$。

3. 主函数 main：

   • ios_base::sync_with_stdio(false); 和 cin.tie(NULL); 用来关闭 C 和 C++ 输入输出的同步，加快读入速度；
   • 用 vector<int> results 存储结果；
   • 循环逐一判断，符合条件的加入 results；
   • 最后根据 results 是否为空，输出 NO 或数组中所有元素（元素间用空格分隔）。

总结

本题是一道基础的质数筛选题，考察了质数判断和数位提取两个基本操作。对于数据范围较大的场景，可以考虑使用埃氏筛或线性筛提前预处理质数表以优化查询，但在本题设定的数据规模内，直接枚举判断已经足够高效。