这是一个用于生成 B3939 [GESP样题 四级] 绝对素数 测试数据的完整 C++ 代码。

由于题目中 $A, B$ 的范围非常小（$10 < A < B < 100$），我们可以手动设计或半随机生成这 10 个测试点，以确保覆盖题目要求的各种情况：

1. 样例数据：验证基础正确性。
2. 最大范围：覆盖所有可能的两位数。
3. 无解区间：测试程序在没有符合条件的数时是否正确（即不输出）。
4. 边界情况：紧贴 $A=11$ 或 $B=99$ 的情况。
5. 特定区间：包含特定绝对素数的区间。

数据生成器代码 (generator.cpp)

你可以将以下代码保存为 generator.cpp，编译并运行。它将在当前目录下生成 1.in/1.out 到 10.in/10.out。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

// ==========================================
// 1. 标准解法函数 (用于生成 .out 文件)
// ==========================================
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

void solve(int A, int B, ostream& out) {
    for (int i = A; i <= B; i++) {
        // 1. 判断 i 本身是否为素数
        if (isPrime(i)) {
            // 2. 计算位置对换后的数
            int tens = i / 10;
            int ones = i % 10;
            int reversed_i = ones * 10 + tens;

            // 3. 判断对换后的数是否为素数
            if (isPrime(reversed_i)) {
                out << i << endl;
            }
        }
    }
}

// ==========================================
// 2. 测试点生成逻辑
// ==========================================
void generate_test_case(int id) {
    int A, B;

    // 根据 id 手动设计具有代表性的测试点
    // 题目约束: 10 < A < B < 100
    switch (id) {
        case 1: // 样例数据
            A = 11; B = 20;
            break;
        case 2: // 最小合法边界 (紧贴下界)
            A = 11; B = 12; 
            break;
        case 3: // 最大合法范围 (全覆盖)
            A = 11; B = 99;
            break;
        case 4: // 无解区间 1 (20-30 只有 23,29，反转为 32,92 均非素数)
            A = 20; B = 30;
            break;
        case 5: // 包含密集绝对素数的区间 (70-80 有 71, 73, 79)
            A = 70; B = 80;
            break;
        case 6: // 包含 30 段的绝对素数 (31, 37)
            A = 30; B = 40;
            break;
        case 7: // 最大合法边界 (紧贴上界)
            A = 90; B = 99; // 包含 97
            break;
        case 8: // 跨度较小的随机区间 1
            A = 12; B = 15; // 包含 13
            break;
        case 9: // 跨度较大的随机区间
            A = 15; B = 85;
            break;
        case 10: // 无解区间 2 (40-60 之间没有绝对素数)
            // 41->14, 43->34, 47->74, 53->35, 59->95 均不满足
            A = 40; B = 60;
            break;
        default:
            A = 11; B = 99;
    }

    // --- 写入 .in 文件 ---
    string in_filename = to_string(id) + ".in";
    ofstream fin(in_filename);
    fin << A << " " << B << endl;
    fin.close();

    // --- 计算答案并写入 .out 文件 ---
    string out_filename = to_string(id) + ".out";
    ofstream fout(out_filename);
    solve(A, B, fout);
    fout.close();

    cout << "Generated Case " << id << ": A=" << A << ", B=" << B << endl;
}

int main() {
    // 生成 1 到 10 号测试点
    for (int i = 1; i <= 10; ++i) {
        generate_test_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

测试点覆盖说明

1. Case 1: 题目样例 (11 20) -> 输出 11, 13, 17。
2. Case 2: 最小范围 (11 12) -> 测试边界值 11。
3. Case 3: 最大范围 (11 99) -> 输出所有绝对素数 (11, 13, 17, 31, 37, 71, 73, 79, 97)。
4. Case 4: 空结果区间 (20 30) -> 确保程序在无结果时不输出任何内容。
5. Case 5: 密集区间 (70 80) -> 测试 71, 73, 79。
6. Case 6: 普通区间 (30 40) -> 测试 31, 37。
7. Case 7: 最大边界 (90 99) -> 测试边界值 97。
8. Case 8: 小范围包含 (12 15) -> 仅包含 13。
9. Case 9: 大范围混合 (15 85) -> 包含中间大部分。
10. Case 10: 较长空结果区间 (40 60) -> 再次验证无解逻辑。

使用方法

1. 将代码保存为 generator.cpp。
2. 使用 g++ generator.cpp -o generator 编译。
3. 运行 ./generator (Windows 下是 generator.exe)。
4. 生成的 .in 和 .out 文件即为所需的测试数据。

这是一个非常经典的素数判断与模拟题目，适合练习函数的使用和基本的数字位操作。

题目分析

1. 范围限制：题目保证输入 $A$ 和 $B$ 在 10 到 100 之间，即我们只需要处理两位数。
2. 绝对素数定义：
   • 条件1：本身是素数。
   • 条件2：个位和十位交换后形成的新的两位数也是素数。
3. 算法流程：
   • 编写一个判断素数的函数 isPrime(n)。
   • 遍历 $A$ 到 $B$ 之间的每一个数 $i$。
   • 首先判断 $i$ 是否为素数。
   • 如果是，算出交换后的数 reverse_i（个位变十位，十位变个位）。
   • 再判断 reverse_i 是否为素数。
   • 如果两个条件都满足，输出 $i$。

C++ 参考代码

#include <iostream>

using namespace std;

// 判断一个整数是否为素数
// 如果是素数返回 true，否则返回 false
bool isPrime(int n) {
    if (n < 2) return false; // 小于 2 的数不是素数
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false; // 如果能被整除，则不是素数
        }
    }
    return true;
}

int main() {
    int A, B;
    // 读入范围 A 和 B
    cin >> A >> B;

    // 遍历 A 到 B 之间的每一个数
    for (int i = A; i <= B; i++) {
        // 1. 判断 i 本身是否为素数
        if (isPrime(i)) {
            // 2. 计算位置对换后的数
            // 对于两位数，i / 10 得到十位，i % 10 得到个位
            int tens = i / 10;
            int ones = i % 10;
            int reversed_i = ones * 10 + tens;

            // 3. 判断对换后的数是否为素数
            if (isPrime(reversed_i)) {
                cout << i << endl;
            }
        }
    }

    return 0;
}

知识点解析

1. 素数判断：isPrime 函数利用了试除法。只需要尝试除以 $2$ 到 $\sqrt{n}$ 之间的整数即可。对于 100 以内的数，循环次数非常少，效率很高。
2. 位分离与重组：
   • 获取十位：i / 10（整除）。
   • 获取个位：i % 10（取模）。
   • 重组：个位 * 10 + 十位。
3. 逻辑判断：利用嵌套的 if 语句或者逻辑与 && 运算符来确保两个条件同时满足。

时间复杂度分析

外层循环O（n），内层循环检查因素O(根号n），一共O（n2根号n），在n约等于1e6时会超时

时间复杂度优化思路

使用空间换时间，提前用质数筛把范围内的质数筛一遍，然后查表判断质数，避免内层循环判断质数。